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

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Binary Tree:

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.

–EOF (The Ultimate Computing & Technology Blog) —