3 ms·

A breadth-first search can be easily handled with recursion (in fact, I'd argue the specification is almost as simple): def bfs(search_node, nodes_to_visit):

A breadth-first search can be easily handled with recursion (in fact, I'd argue the specification is almost as simple): def bfs(search_node, nodes_to_visit): node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.neighbors) return bfs(search_node, nodes_to_visit) bfs(search_node, [root_node])

btilly 16y ago
If it is so easy, why does your implementation crash if the element is not in the tree? :-P After you fix that minor bug, you'll find that your code crashes for trees with over 1000 nodes. That is also easy to fix. But in any language without tail recursion, your implementation hits the stack hard. Which in many multi-threaded environments may not be not a wise thing to do. All that said, I submit that you easily think of that version because you're familiar with how the recursive solution manages the stack. If you're familiar with that, then switching from dfs to bfs is just a question of replacing a stack with a queue. Compare: def dfs(search_node, root_node): nodes_to_visit = [root_node] while 0 < len(nodes_to_visit): node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.children) return None def bfs(search_node, root_node): nodes_to_visit = [root_node] while 0 < len(nodes_to_visit): node = nodes_to_visit.pop(0) if node == search_node: return node else: nodes_to_visit.extend(node.children) return None Now contrast the two obvious recursive variations. def dfs_recursive(search_node, root_node): if search_node == root_node: return root_node for child_node in root_node.children: answer = dfs_recursive(search_node, child_node) if answer is not None: return answer return None def bfs_recursive(search_node, root_node): nodes_to_visit = [] def _recurse(): if 0 == len(nodes_to_visit): return None node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.children) return _recurse() return _recurse()
- infinite8s 16y ago
  Well, I agree with you there. Any language that can't handle proper tail recursion makes it really difficult to safely implement a recursive solution. But I often find it easier to solve a problem with a recursive solution and perform an almost mechanical conversion into the corresponding iterative solution. (also I'm embarrassed that I forgot the edge case where the node is not in the tree)
  - btilly 16y ago
    We all make silly errors. Your bfs was a complicated dfs, and neither of us noticed. (In fact I copied your code and edited it, and had dfs and bfs reversed.) Luckily I was able to edit my node to hide my variation of the error.

btilly 16y ago

If it is so easy, why does your implementation crash if the element is not in the tree? :-P After you fix that minor bug, you'll find that your code crashes for trees with over 1000 nodes. That is also easy to fix. But in any language without tail recursion, your implementation hits the stack hard. Which in many multi-threaded environments may not be not a wise thing to do. All that said, I submit that you easily think of that version because you're familiar with how the recursive solution manages the stack. If you're familiar with that, then switching from dfs to bfs is just a question of replacing a stack with a queue. Compare: def dfs(search_node, root_node): nodes_to_visit = [root_node] while 0 < len(nodes_to_visit): node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.children) return None def bfs(search_node, root_node): nodes_to_visit = [root_node] while 0 < len(nodes_to_visit): node = nodes_to_visit.pop(0) if node == search_node: return node else: nodes_to_visit.extend(node.children) return None Now contrast the two obvious recursive variations. def dfs_recursive(search_node, root_node): if search_node == root_node: return root_node for child_node in root_node.children: answer = dfs_recursive(search_node, child_node) if answer is not None: return answer return None def bfs_recursive(search_node, root_node): nodes_to_visit = [] def _recurse(): if 0 == len(nodes_to_visit): return None node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.children) return _recurse() return _recurse()

infinite8s 16y ago
Well, I agree with you there. Any language that can't handle proper tail recursion makes it really difficult to safely implement a recursive solution. But I often find it easier to solve a problem with a recursive solution and perform an almost mechanical conversion into the corresponding iterative solution. (also I'm embarrassed that I forgot the edge case where the node is not in the tree)
- btilly 16y ago
  We all make silly errors. Your bfs was a complicated dfs, and neither of us noticed. (In fact I copied your code and edited it, and had dfs and bfs reversed.) Luckily I was able to edit my node to hide my variation of the error.