Ways to traverse a binary tree: using the recursive and iterative approach

In order to know a binary tree’s structure and nodes detail, normally, there are four ways to traverse a tree: pre-order traversal, in-order traversal, post-order traversal, and level order traversal. In this post, I’ll introduce these traversals and implement them using Python both in the recursive and iterative approach. I’ll use the following graph as an example of a binary tree in this post.

Pre-order traversal

‘pre’ is standing for ‘prefix’. Following the order this -> left -> right when traveling a binary tree from the root node. For the given binary tree, we start with root 4, then go to the left node 2, then treat the node 2 as ‘this’ node, start the pre-order again until we traversal the whole tree. The pre-order result: [4,2,1,3,6,5,7].

Recursive solution:

Applying recursion on this problem is trivial. Following the path, we just need to visit the current node, then recursively visit the left subtree and right subtree:

def preorderTraversal(root):
    if not root:
        return []
        
    return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)

Iterative solution:

We can have a stack to store the current node’s info. Then we iteratively push the right and left node to the stack. The last node’s value is the current node’s value.

def preorderTraversal(root):
    stack, result = [root], []   
    while stack:
        curr = stack.pop()
        if curr:
            result.append(curr.val)
            stack.append(curr.right)
            stack.append(curr.left)
        
    return result

In-order traversal

In-order traversal is the most common used on binary search tree, is following the path: left -> this -> right. When applying this to a binary search tree, the printed order is in ascending order. For the given binary tree, the result is: [1,2,3,4,5,6,7]

Recursive solution:

Similar to the previous recursion code, here we only need to modify the order to left -> this -> right:

def inorderTraversal(root):
    if not root:
        return []
        
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

Iterative solution:

First, we need to locate the left-most node. Then, record this node’s value. Finally, to see if this node has the right node.

def inorderTraversal(root):
    stack, result = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
            
        node = stack.pop()
        result.append(node.val)
        curr = node.right 
    return result

Post-order traversal

Contrary to the pre-order traversal, post-order is visiting the children nodes first, then visit the self node. The path is: left -> right -> this. For the given binary tree, the result is: [1,3,2,5,7,6,4].

Recursive solution:

Similar to the previous recursion code, here we only need to modify the order to left -> right -> this:

def postorderTraversal(root):
    if not root:
        return []
        
    return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]

Iterative solution:

The inverse order for post order is this->right->left, we can implement the code using the inverse order, then inverse the result.

def postorderTraversal(root):
    nodes, result = [root], []
        
    while nodes:
        curr = nodes.pop(0)
        if curr:
            result.insert(0, curr.val)
            nodes.insert(0, curr.left)
            nodes.insert(0, curr.right)
        
    return result

Level-order traversal

As it sounds like, level-order traversal is visiting a tree in level order from top to bottom. For the given binary tree, the result is: [[4],[2,6],[1,3,5,7]].

Iterative solution:

The level-order is often solved iteratively, or Breadth-first search. It utilizes a queue to store the nodes in a given order, the order could be left->right or right->left. Then we constantly dequeue and enqueue a node, until the tree is fully visited.

def levelOrder(root):
    if not root:
        return []
        
    queue, result = [root], []
        
    while queue:
        size = len(queue)
        level = []
        for _ in range(size):
            curr = queue.pop(0)
            level.append(curr.val)
            if curr.left: queue.append(curr.left) 
            if curr.right: queue.append(curr.right) 
        result.append(level)
        
    return result