poctek - 1 year ago 82

Ruby Question

I have some troubles with recursive method for depth first search algorithm implementation. Here's the binary tree photo:

The method works well with the right side of the tree (55, 89, 144), but it returns nil when it comes to the left side, even though it puts "yes". So, what's wrong with the code? The node is an instance of Node class that has value (integer) and links to the left and right child (other instances of Node class) which is nil if it doesn't have the child from that side.

Here's the method code:

`def depth_first_search(node, target)`

if node.value == target

puts "yes"

return node

end

depth_first_search(node.child_left, target) if node.child_left

depth_first_search(node.child_right, target) if node.child_right

end

Answer

Because `depth_first_search(node.child_left, target)`

isn't the last line of your method, its value will never be returned. You need to return its value if its value is not `nil`

. Here is an example of one way to solve your problem:

```
def depth_first_search(node, target)
if node.value == target
puts "yes"
return node
end
left = depth_first_search(node.child_left, target) if node.child_left
right = depth_first_search(node.child_right, target) if node.child_right
left or right
end
```

Note that this example will search the right subtree even if the correct node is found on the left subtree, which is inefficient.

Source (Stackoverflow)