Inorder Traversal Without Recursion

Binary Tree

What is a Binary Tree ?

A Binary Tree is a data structure which follows a hierarchical structure. It begins with a root node, (basically when you pass a binary tree as a data structure you pass the location of the root or the root itself) and continues downwards. Each node including the root node can have a minimum of 0 children and a maximum of 2 children. The two children are known as the left child of the node and the right child of the node. If we follow a indexing method where the index of a node is say i, (usually root node starts with index 1) then its left child will have index 2 * i and right child will have index 2 * i + 1.

What is Inorder ?

The nodes of a binary tree can be traversed in three ways namely preorder, inorder and postorder. Inorder Traversal means traveling in the order,

Left Child -> Root -> Right Child (Inorder traversal)

The preorder and postorder being as follows,

Root -> Left Child -> Right Child (Preorder Traversal)
Left Child -> Right Child -> Root (Postorder Traversal)

Let’s Solve it with Recursion First !

The problem becomes very easy with recursion. But understanding the recursion solution is very essential to be able to come up with an iterative solution. The inorder traversal essentially means we will traverse the left child of every node first then the node iteself and then the right child.

Pretty Simple Right ? Yes, the code is also very easy ! Let’s have a look at it.

def inorderTraversal(root: TreeNode) -> [int]:
    inorder = []
    def traverse(node: TreeNode):
        if node == None:
            return
        traverse(node.left)
        inorder.append(node.val)
        traverse(node.right)
        return
    traverse(root)
    return inorder

The code talks for itself. The function traverse has a base case that returns when the node is None. Otherwise, it will move to the left subtree first then come back to the node append it to the array, and then go on to traverse the right subtree.

Understanding What Actually Happens in the Recursion

In the recursive function the function, keeps calling itself on its left child until an unless it finds a node that has no left child. It then takes the value of the node and starts traversing the right child. For the right child as well it will keep traversing the left side of it till it hits a node that has no left child and then come back to the node and continue the same process so on and so forth.

Now to translate this recursive code into a iterative one we first need to figure out which data structure we can use to achieve this. When the recursion function is called time and again the previous recursion is always stored in the call stack until and unless a base case is hit and it then starts to trace its way back by resuming the action where it left. Then it starts pushing the nodes of the right subtree into the call stack until there is a node with no left child. Once such a node is found the recursion keeps tracing back.

By understanding the recursion in this way we can easily build up the logic of using a stack to keep pushing nodes into it until we get a node with no left child. Once we get such a node we can pop a node out, and then start pushing its right subtree in the same way.

And Now Let’s Do It Without Recursion

1) Create a stack that will contain nodes
2) Create an array that will contain the inorder traversal of the tree
3) Initialize the current_node to the root element. We will keep moving deep into the left subtree of the root until the current root becomes none
4) Once the current root becomes none, now we can trace our path back by poping the elements from the stack and now traversing the right subtree of the particular node in the same manner as stated above
5) The Loop terminates once the stack is empty and the current node becomes None, which would essentially mean that there are no nodes left to be explored.

def inorderTraversal(root: TreeNode) -> [int]:
    inorder = []
    nodes = []
    current_node = root
    while len(nodes) != 0 or current_node != None:
        if current_node == None:
            current_node = nodes[-1]
            nodes.pop()
            inorder.append(current_node.val)
            current_node = current_node.right
        else:
            nodes.append(current_node)
            current_node = current_node.left
    return inorder