# Breadth and Depth First Search in Ruby

Posted on

Problem

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
``````

``````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])

depth_first_search(7, binary_tree)
``````

Solution

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 `Node`s, 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 `puts`ing your return values instead of using those arrays you love so much? And why do you `exit` instead of `return`ing? 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.