Implementing Preorder Traversal in a Binary Tree (recursive approach)

In this article we’ll see how to implement the pre-order traversal in a binary tree. Once we see the solution then we can also implement in-order as well as post-order traversals just by making some changes in our code.

Let’s start by seeing how preorder traversal works in a binary tree. Let’s take the simplest example first.

simplest form of binary tree

In the above example we have a binary tree which has a root node and two child nodes (left and right).

In a Pre-order traversal we visit the Root node first then the left subtree and finally we traverse the right subtree. So in the above example after implementing pre-order traversal we’ll get the nodes in the order — [9,3,2]

But what if the depth of our tree is large?

let’s take another example

binary tree with a depth of 3

In the above example we have a binary tree of depth 3. Implementing pre-order traversal in the above tree will be slightly difficult than the previous example. we will store the values of nodes in an empty array.

First we’ll visit the root node which is 9. After that the left subtree so go to 3. Our array after these two nodes will be — [9]

Now before we visit 2 we need to check whether 3 has any children or not. In this case it has two child nodes 4 and 7 and hence 3 will be the root node for these two nodes so we insert 3 into our array and then go to the left that is 4. now 4 doesn’t has any child nodes so we will insert 4 and then go to 7 and insert it as well because it also doesn’t has any child nodes. Our array after insertions will be — [9,3,4,7]

we repeat the same process then on the right subtree i.e.- go to 2 then 2 will be root for 8 and 10 and after inserting all the values our final array will be — [9,3,4,7,2,8,10]

Implementation in code can done in both iterative and recursive ways. We’ll see the recursive

Let’s see the code for recursive approach

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

Our first if statement check if the root node is empty and returns and empty array in case of true. else we go into our recursive logic.

We declare an empty array to store the values of the nodes we visit and since we go from root, left and right we will append the value of root to our array first.

After that we check if the root node contains any left or right subtree. If it does then we call our function again and pass root.leftor root.right depending on the condition. And since our function just appends a single value to the array calling the function again will give us another array of single element which we add to our val_arr because in the end we want to return our val_arr.

The recursion will stop once we reach the leaf nodes. And the reason why this code works is because there is repetition in a binary tree

repetition in a binary tree

3 becomes a root node for 4 and 7 so we can call the function again on 3 i.e.- preorderTraversal(3) which will then insert value of 3 into the array and then again call the function on 4 and 7 (preorderTraversal(4) and preorderTraversal(7)). The same thing will happen on the right subtree as well and once we reach the leaf nodes the recursion will stop.

Our final array will be [9,3,4,7,2,8,10]. The time complexity of this approach is O(N) as we are visiting each node once and the space complexity is O(N) as well, since each function call will occupy space in the stack.

You can implement in-order and post-order traversals in the same way by just changing the position of the line of code where you append the value of the node into the array.

In-order raversal code implementation

def inorderTraversal(root):
    if not root:
        return []
    else:
        val_arr = []  
        if root.left:      
            val_arr += self.inorderTraversal(root.left)
                
        val_arr.append(root.val)
            
        if root.right:
            val_arr += self.inorderTraversal(root.right)
    return val_arr

Post-order traversal code implementation

def inorderTraversal(root):
    if not root:
        return []
    else:
        val_arr = []
            
        if root.left:
            val_arr += self.postorderTraversal(root.left)
            
        if root.right:
            val_arr += self.postorderTraversal(root.right)
                
        val_arr.append(root.val)
            
        return val_arr

Iterative approach —

Pre-order traversal of binary tree (iterative approach)