Pre-order traversal of binary tree(iterative approach)

In the last article I showed the recursive implementation of pre-order traversal of binary tree. In this article I’ll show the same algorithm but in iterative approach. The previous article is given below.

Implementing Preorder Traversal in a Binary Tree (recursive approach)

Let’s take an example

We well use a stack to push the left and right nodes of root and continue to loop till the stack is empty. First we push the root node into the stack and then we loop till stack becomes empty.

In the first iteration there will only be root node in the stack which will be then popped off and inserted into our values array.

After that we push the left and right child of the root node into the stack (right first then left so while popping we pop the left first) and continue till the stack is empty.

1st iteration root(9) will be popped off and then right(2) and left(3) will be pushed

3 will be popped and it’s left(4) and right(7) child will be pushed onto the stack

4 will be popped then 7 will be popped since 4 and 7 are leaf nodes

After 4 is popped from the stack 7 will also be popped since 4 doesn’t has any left and right nodes.

So our values array till now will become — [9,3,4,7]. The loop will still continue because we still have 2 in our stack

2 will then be popped off and 10 and 8 will pe pushed onto the stack. loop will still continue because we still have two nodes in stack.

8 and 10 will be popped off from the stack and inserted into our values array. There won’t be any new addition to the stack since 8 and 10 are the leaf nodes and the stack will be empty. Hence we will now exit the loop and return our values array. [9,3,4,7,2,8,10].

Below is the code implementation of the algorithm

def preorderTraversal(root):
    if not root:
        return []
    else:
        val_arr = []
        stack = []
        currentnode = root
        
        stack.append(currentnode)
            
        while (len(stack) > 0):
            currentnode = stack.pop()
            val_arr.append(currentnode.val)
                
            if currentnode.right:
                stack.append(currentnode.right)
                
            if currentnode.left:
                stack.append(currentnode.left)
    return val_arr

The iterative approaches for in-order and post-order traversals also use stack but the implementation is different.