Finding path to node using Breadth First Search

Question

I have a binary tree and I want to implement the Breadth first search algorithm to search for a node in the tree. I have managed to make some sort of tree, and I want to make a function for BFS where it prints out the path to a selected node. How do I make such a function?

class Node: 

# A utility function to create a new node 
def __init__(self, key): 
    self.data = key  
    self.left = None
    self.right = None

root = Node('A') 
root.left = Node('B') 
root.left.left = Node('D')
root.left.right = Node('E')
root.left.left.left = Node('G')
root.left.left.right = Node('H') 
root.left.right.right = Node('K')
root.left.right.left = Node('I')
root.left.right.left.left = Node('K')

BFS is described all over the internet. Why did you not take inspiration from that? Like from [Wikipedia](https://en.wikipedia.org/wiki/Breadth-first_search)? — trincot, Oct 16 '20 at 21:34

score 1 · Accepted Answer · answered Oct 16 '20 at 19:08

You can do a standard BFS using a queue, but add the path to that node as part of the state in the queue.

from collections import deque

class Node: 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None

def path_from_to(root, target):
    queue = deque([(root, [root.data])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        if node.left:
            queue.append((node.left, path + [node.left.data]))
        if node.right:
            queue.append((node.right, path + [node.right.data]))

if __name__ == "__main__":
    root = Node('A')
    root.left = Node('B') 
    root.left.left = Node('D')
    root.left.right = Node('E')
    root.left.left.left = Node('G')
    root.left.left.right = Node('H') 
    root.left.right.right = Node('K')
    root.left.right.left = Node('I')
    target = Node('K')
    root.left.right.left.left = target
    print(path_from_to(root, target))

Output:

['A', 'B', 'E', 'I', 'K']

Since it's a tree, we don't need to keep a list of previously visited nodes.

Note that DFS is usually a bit better suited for searching in trees.

How would a depth first search look like in this example? – Andres Hansen Oct 16 '20 at 20:36 — Andres Hansen, Oct 16 '20 at 20:36

Alain T. · Answer 2 · 2020-10-16T21:15:52.090

Alternatively you can use an approach that requires more processing but less memory (than a queue):

The node class itself can provide iterators that will traverse nodes in a breadth first order either top down or bottom up.

class Node:
    
    def __init__(self, value): 
        self.value = value  
        self.left  = None
        self.right = None
        
    @property
    def maxLevel(self):
        return max(self.left.maxLevel+1  if self.left  else 0,
                   self.right.maxLevel+1 if self.right else 0)

    def topDown(self):
        for depth in range(self.maxLevel+1):
            for node in self.nodesAtLevel(depth): yield node

    def bottomUp(self):
        for depth in range(self.maxLevel,-1,-1):
            for node in self.nodesAtLevel(depth): yield node
            
    def nodesAtLevel(self,depth,level=0):        
        if level == depth:
            yield self  # output node when at requested depth
            return 
        for subNode in (self.left,self.right): # reach deeper
            if not subNode: continue
            for node in subNode.nodesAtLevel(depth,level+1):
                yield node

output:

root           = Node('A') # level 0
B = root.left  = Node('B') # level 1
D = B.left     = Node('D') # level 2
E = B.right    = Node('E') # level 2
G = D.left     = Node('G') # level 3
H = D.right    = Node('H') # level 3 
K = root.right = Node('K') # level 1
I = K.left     = Node('I') # level 2

for node in root.topDown(): print(node.value)

# A B K D E I G H

for node in root.bottomUp(): print(node.value)

# G H D E I B K A

You could also extend the class even more to add other types of traversal iterators:

    def leftToRight(self):
        if self.left:
            for node in self.left.leftToRight(): yield node
        yield self
        if self.right:
            for node in self.right.leftToRight(): yield node

    def rightToLeft(self):
        if self.right:
            for node in self.right.rightToLeft(): yield node
        yield self
        if self.left:
            for node in self.left.rightToLeft(): yield node

To implement your path function using breadth first search, you should use the bottom up function and append parents as you find them (since parents will appear after children in that order):

    def BFPath(self,node):
        path = [node]
        for parent in self.bottomUp():
            if path[-1] in [parent.left,parent.right]:
                path.append(parent)
        return path[::-1]

example use:

print([n.value for n in root.BFPath(H)])

# ['A', 'B', 'D', 'H']

Finding path to node using Breadth First Search

2 Answers2