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)

• Nakilon: You may be interested in: codereview.stackexchange.com/q/65007/665
• greybeard: Is visited any use in breadth_first_search()?

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.