Breadth and Depth First Search in Ruby

Question

I was tasked with building three individual methods; one to create a Binary Search Tree (BST), one to carry out a Breadth First Search (BFS), and one to carry out a Depth First Search (DFS).

Create Binary Tree

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
  end
end

def build_tree(array, *indices)
  array.sort.uniq!
  mid = (array.length-1)/2
  first_element = indices[0]
  last_element = indices[1]

  if !first_element.nil? && first_element >last_element
    return nil 
  end

  root = Node.new(array[mid])
  root.left = build_tree(array[0..mid-1], 0, mid-1)
  root.right = build_tree(array[mid+1..-1], mid+1, array.length-1)

  return root
end

Breadth First Search

def breadth_first_search(search_value, tree)
  queue = [tree]
  visited = [tree]

  while !queue.empty? 
    current = queue.shift
    visited << current
    left, right = current.left, current.right

    if current.value == search_value
      puts current
      exit
    end

    if !left.nil? && !visited.include?(left)
      if left.value == search_value
        puts left
        exit
      else
        visited << left
        queue << left
      end
    end

    if !right.nil? && !visited.include?(right)
      if right.value == search_value
        puts right
        exit
      else
        visited << right
        queue << right
      end
    end
  end
  puts "nil"
end

Depth First Search

def depth_first_search(search_value, tree)
  stack = [tree]
  visited = [tree]

  while !stack.empty?
    current = stack.last
    left, right = current.left, current.right

    if current.value == search_value
      puts current
      exit
    elsif !left.nil? && !visited.include?(left)
      if left.value == search_value
        puts left
        exit
      else
        visited << left
        stack << left
      end
    elsif !right.nil? && !visited.include?(right)
      if right.value == search_value
        puts right
        exit
      else
        visited << right
        stack << right
      end
    else
      stack.pop
    end
  end
  puts "nil"
end

Calling the Methods

binary_tree = build_tree([4,7,2,8,1,1,1,30,22,4,9])

breadth_first_search(9, binary_tree)
depth_first_search(7, binary_tree)

Answer 1

1. Why do you have a build_tree function instead of a BST class with a constructor? It can just be a container to wrap around Node, but that way you can encapsulate things better. Generally, a BST isn't used because people want access to the tree structure, but because it's being used as a min heap or for quicker searching than O(n). If you really want to, you can expose the Nodes, but it'd still be better to wrap it in a class, if only so that...
2. ...You can write your search functions as methods on the tree class. That would make more sense than passing in a parameter which is, essentially, self.
   1. You could then make more convenience methods, like insert and remove, which would allow you to easily create trees from unsorted arrays and provide those methods to the caller.
3. Use a Set for your visited collection, unless you really like O(n), as opposed to O(1). lookup.
4. Likewise, use a Queue for your queue. That way you get O(1) enqueue and dequeue; with a normal array, one of the two is O(1), but the other is O(n) (depending on which end you enqueue and dequeue from)
5. I'd bet you can guess what I'm gonna say about your stack variable. But you're wrong! Haha, fooled you! Anyway, an array is fine for that, since (a) there's no Stack class in the Ruby standard library, at least as far as I'm aware, and arrays have O(1) push/pop if you use the methods with those names (which you do), as long as it never needs to resize to accommodate more elements. Even if it does, though, that happens relatively rarely; it's normally O(1).
6. Why are you putsing your return values instead of using those arrays you love so much? And why do you exit instead of returning? What if I want to run your example and see both outputs?
7. All in all, this code doesn't feel very Ruby-ish -- it seems more like a straight translation from the C++ equivalent. However, I can't think offhand of an elegant, straight-forward way to do the same thing, so I'm just going to leave you with this vague admonishment.
8. On second thought, scratch #6. I didn't really pay attention to what you were doing, but you shouldn't replace puts with return. Instead, if you reach the end, return false; if you find an equal element, return either true or the path you took to get there, if the path is that important.

---

It's worth noting that there's no point in making this a binary search tree if you're going to do a brute-force search every time. The point of a BST is that, at any given node, you can compare what you're looking for with the data of that node, and figure out if you have to go left or right or if you've found it, and thereby eliminate the need for breadth-first searching in general.

If you're only going to have B/DFS, just make it a generic tree, and don't bother with that fancy stuff about ordering and the like that you have in your "constructor". That'll be a better test, anyway, since a B/DFS is typically used in cases where you don't have ordering. If you really wanna keep the ordering, try writing a binary search; it's a fun little exercise.

Answer 2

Your prose announces a Binary Search Tree (BST), the "code block title" Create Binary Tree; the code fits the latter.

In build_tree() you use uniq! which modifies… a sorted copy abandoned immediately: No effect on the original. (I can see a reason why not wanting to build the tree from the ordered array.)
If it worked, it would not be useful in any recursive invocation.
This recursive procedure builds a tree somewhat height balanced.
*indices gets used for termination, only:
either don't slice and use them for indexing
or don't introduce them at all.

In breadth_first_search() using puts when search_value is found mixes mechanism (finding a value/node by key) with business (handling the search result).
There are three places search_value gets compared to a node's value - this just doesn't look right.
(I did not find a convincing Ruby documentation convention - hyperlink & fix comments if you know better)

# returns Node if found, else "nil"
def breadth_first_search(search_value, tree)
  queue = Thread::Queue.new
  queue << tree

  while !queue.empty? 
    current = queue.shift
    if current.nil?
      next
    end
    # puts "v #{current.value} n #{current}"
    if current.value == search_value
      return current
    end
    queue << current.left << current.right
  end
  "nil"
end

# (similarly:)
# returns Node if found, else "nil"
def depth_first_search(search_value, tree)
  stack = [tree]
#  visited = Set

  while !stack.empty?
    current = stack.pop
    if current.nil?
      next
    end
    if current.value == search_value
      return current
    end
    stack.push(current.right).push(current.left)
  end
  "nil"
end

Using shift to dequeue and << to enqueue is annoyingly asymmetrical - better use enq/deq?
In depth_first_search(), using a stack and pushing left before right leads to visit order right, left.