# Teaching Kids Programming – Converting Breadth First Search Algorithm to Iterative Preorder Order (Depth First Search) for a Binary Tree

Teaching Kids Programming – Converting Breadth First Search Algorithm to Iterative Preorder Order (Depth First Search) for a Binary Tree | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Binary Tree:

The level-by-level order can be done via Breadth First Search Algorithm where we use a queue (e.g. double-ended queue). The order is 4-85-016 for the above binary tree.

The standard BFS code for performing a level-by-level order in a given binary tree (root):

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```def bfs(root):     if root is None:         return     q = deque([root])     while q:         cur = q.popleft()         yield cur         if cur.left:             q.append(cur.left)         if cur.right:             q.append(cur.right)```
```def bfs(root):
if root is None:
return
q = deque([root])
while q:
cur = q.popleft()
yield cur
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)```

If we change the queue (dequeu) to stack, and replace the popleft() with pop() as we are taking from the top of the stack – this will become a Reverse Preorder Traversal algorithm – NRL (Node-Right-Left):

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```def reversePreorder(root):     if root is None:         return     q = [root]     while q:         cur = q.pop()         yield cur         if cur.left:             q.append(cur.left)         if cur.right:             q.append(cur.right)```
```def reversePreorder(root):
if root is None:
return
q = [root]
while q:
cur = q.pop()
yield cur
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)```

As the stack push/pop gives the reverse order, we can swap around the pushing of left and right nodes, that is, push the right nodes and then left node, this will give the Preorder Traversal Algorithm.

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```def preorder(root):     if root is None:         return     q = [root]     while q:         cur = q.pop()         yield cur         if cur.right:             q.append(cur.right)         if cur.left:             q.append(cur.left)```
```def preorder(root):
if root is None:
return
q = [root]
while q:
cur = q.pop()
yield cur
if cur.right:
q.append(cur.right)
if cur.left:
q.append(cur.left)```

If implementeed using Recursion, the Recursive Preorder Traversal Algorithm:

 ```1 2 3 4 5 6 ``` ```def preorder(root):     if root is None:         return     yield cur     yield from preorder(root.left)     yield from preorder(root.right)```
```def preorder(root):
if root is None:
return
yield cur
yield from preorder(root.left)
yield from preorder(root.right)```

The time/space complexity for the above traversal algorithms are O(N) where N is the number of the nodes in the given binary tree.

GD Star Rating