Tree Traversal – Recursively & Iteratively

Tree traversal refers to the process of visiting each node in a tree data structure (Wikipedia). The two general strategies are Depth-First-Search (DFS) and Breadth-First-Search (BFS). For BFS, it iterates through the tree level by level with Queue, from top to bottom. When using DFS, there are three different ways: Preorder, Inorder, and Postorder.

If we use V, L, and R to represent visiting the current node, moving to the left subtree, and moving to the right subtree, there are 6 possible traversals: VLR, VRL, LVR, RVL, LRV, RLV. If the left node is constrained to be visited before the right node, only three traversals remain: VLR, LVR, and LRV, with the names of Preorder traversal, Inorder traversal, and Postorder traversal accordingly.

To traverse a tree – follow the numbers from 1 to 5 to visit nodes in different orders.

We can implement each of them using recursions with the system’s execution stack and using iterations with a self-defined stack. Notably, the key differences between recursions and iterations are:

  1. A conditional statement determines the exit of a recursion, while a control variable’s value determines the termination of an iteration.
  2. Infinite recursions lead to stack overflow, while infinite iterations consume CPU cycles.
  3. Sometimes recursions are comparatively slower than iterations.

Preorder – V L R

To traverse a tree in preorder, we need to:

  1. Visit the current node
  2. Move to the left subtree and start traversing in preorder
  3. Move to the right subtree and start traversing in preorder

Recursion

def preorder(node):
    if node is None:
        return
    visit(node)
    preorder(node.left)
    preorder(node.right)

Iteration

stack = [root]
while stack:
    node = stack.pop()
    visit(node)
    # push the right node to the stack before the left one
    if node.right:
        stack.append(node.right)
    if node.left:
        stack.append(node.left)

Or, we don’t really have to push every node into the stack – for each subtree, we push the right child into the stack and access the left child – to save space.

stack = [root]
while stack:
    node = stack.pop()
    while node:
        visit(node)
        if node.right:
            stack.append(node.right)
        node = node.left

Inorder – L V R

To traverse a tree in inorder, we need to:

  1. Move to the left subtree and start traversing in inorder
  2. Visit the current node
  3. Move to the right subtree and start traversing in inorder

Recursion

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

Iteration

stack = []
cur = root
while stack or cur:
    if cur:
        stack.append(cur)
        cur = cur.left
    else:
        cur = stack.pop()
        visit(cur)
        cur = cur.right

Postorder – L R V

To traverse a tree in postorder, we need to:

  1. Move to the left subtree and start traversing in postorder
  2. Move to the right subtree and start traversing in postorder
  3. Visit the current node

Recursion

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Iteration

When we implement the traversal in preorder, we access the node first, and then push the right child and left child into the stack. So for postorder, are we merely switch the orders of these operations – push the right and left child into the stack and access the node?

The answer is NO – after switching, we are still traversing in preorder. Because what defines preorder is not accessing the node before pushing its children into the stack, but is poping the node out of the stack before pushing the children into it.

However, it does not work for postorder. To implement the iterative way of traversing in postorder, we notice that LRV (postorder) is the reversed VRL (modified preorder).

We visit nodes in VRL with the first stack – by switching L and R in VLR (preorder) – and push the nodes into the second stack. After pushing the tree into the stack, we pop it one by one. Now we have the postorder!

stack = [root]
while stack:
    node = stack.pop()
    reverse_stack.append(node)
    if node.left:
        stack.append(node.left)
    if node.right:
        stack.append(node.right)

while reverse_stack:
    visit(reverse_stack.pop())

Practices

Leetcode problems are available here: [Leetcode for Interview] BinaryTree Traversal – DFS & BFS

References
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments