Postorder Traversal of Binary Tree

Data structures and algorithms form a big portion of the topics you need to cover when it comes to tech interview preparation. Software engineers or developers need to be masters of the basics to be able to solve the tough problems presented at FAANG and tier-1 tech company interviews. In this article, we will cover a few important topics that will help you in your prep — inorder tree traversal, preorder tree traversal, postorder tree traversal, and level-order traversal.

Specifically, we’ll cover:

• What Is Tree Traversal? 
• Inorder Tree Traversal
• Preorder Tree Traversal
• Postorder Tree Traversal
• Level-order Tree Traversal
• Implementation of Tree Traversal
• Time and Space Complexity of Tree Traversal Algorithms
• Examples of Tech Interview Questions on Tree Traversals 
• FAQs on Tree Traversals 

Introduction

A tree is a hierarchical data structure, its property to store the information in a hierarchy makes it different from linear data structures like linked lists, stacks, and others. The tree contains nodes(data) and edges (which connect two nodes) that do not form cycles.  

Traversing the tree means visiting all the nodes in the tree. For example, you can find the sum of all of the values stored in the tree nodes or find the largest one. For all of these operations, we need to visit every node in the tree. 

For linear data structures, such as arrays, stacks, queues, and linked lists, there is only one way to store the data. However, in a hierarchical data structure, such as a tree, we can store the data in many ways. 

What Is Tree Traversal? 

Tree traversals are the algorithms used to traverse the tree in different orders. Each of these algorithms can be defined recursively. In tree traversals, we visit each node in a tree and perform some operations on it, like printing the nodes, etc. 

Tree traversal algorithms are classified into two:

We can picture a tree as a recursive structure; DFS traversals can be implemented recursively. When we’re at a node, three actions can occur: perform some operation on the current node (like print the value stored in it), traverse the left subtree, and traverse the right subtree. Based on this nature, we have the following types of DFS traversal of a tree: 

• Tree Traversal Inorder: In inorder tree traversal, we traverse left, perform some operation on the current node (in this article, we are printing the value stored in it), then traverse right.
• Tree Traversal Preorder: In preorder tree traversal, we perform some operation on the current node, traverse left, traverse right
• Tree Traversal Postorder: In postorder tree traversal, we traverse left, traverse right, Perform some operation on the current node

Inorder Tree Traversal

Inorder tree traversal is one of the most widely used variants of DFS tree traversal.

In inorder tree traversal, we first process the left subtree of the root node, then process the root node, and at last process the right subtree of the root node. Noe let us understand tree traversal inorder with a simple example.

Numbers below each node denote the order in which the nodes are processed.

In the figure above, we first process the left subtree of root node 1. We call a recursive function for the left child of the root, which is 12, and then call recursion again for the left child of 12. We repeat this procedure until we are not on a leaf node. When we reach leaf node 5, there is no child; so, we process node 5 and return to its parent node 12.

We have already processed the left subtree of 12. So, we process node 12 and then call recursion on its right child and process its right subtree as we did the left. This is how we approach inorder tree traversal.

Algorithm and Pseudocode of Inorder Tree Traversal

Algorithm for Tree Traversal Inorder:

Inorder(root)

• Traverse the left sub-tree, (call inorder(left_child).
• Process the root node.
• Traverse the right subtree, (call inorder(right_child).

Psuedocode for Tree Traversal Inorder:

inorder(Node)

   if (Node != null)

       inorder(left_child)

       Process the Node

       inorder(right_child)

   End if

End inorder

Application of Inorder Tree Traversal

Binary search tree or BST is a binary tree with a special property — for every node, the value stored in the left child (if it exists) is smaller than the value stored in the current node. Similarly, the value stored in the right child (if it exists) is greater than the value stored in the current node. For a BST, inorder tree traversal prints the nodes in non-decreasing order. A variation of inorder tree traversal can be used to obtain nodes from BST in non-increasing order.

Preorder Tree Traversal

Preorder traversal is another variant of DFS, where operations in the recursive function are similar to inorder tree traversal but in a different order. 

In preorder traversal, we process the root node, then the left subtree of the root node, and at last process the right subtree of the root node.

In the figure above, we first process the root node 1. After processing the root node, we call a recursive function for the root child's left child, which is 12, and then we process node 12. After that, we call the recursive function on the left child of 12, which is 5, and process it. We repeat this procedure until we are not on a leaf node. There’s no child at leaf node 5. So, after processing node 5, we go back to its parent 12 and then process the right child (the same way we processed its left child). 

Algorithm and Pseudocode Preorder Tree Traversal

Algorithm:

Preorder(root)

• Process the root node.
• Traverse the left sub-tree, (call preorder(root_left).
• Traverse the right subtree, (call preorder(root_right).

Pseudocode:

preorder(Node)

   if (Node != null)

       Process Node

       preorder(left_child)

       preorder(right_child)

   End if

End preorder

‍Applications of Preorder Tree Traversal

We can create a copy of the tree using preorder traversal. Also, preorder traversal can be used to get the prefix expression of an expression. 

Postorder Traversal

Postorder traversal is another variant of DFS. Here, operations in recursive function are similar to the inorder and preorder traversal but in a different order. In postorder traversal, we visit the left subtree nodes first and then traverse to the right subtree and visit nodes in it, and at last, we process the current node. 

Similar to what we did in preorder and inorder tree traversals, in postorder traversal, we first process the left subtree, then the right subtree, and at last, the root node. 

In the figure above, we first process the left subtree until we reach the leaf node. So, the first recursion will be called for the left child of node 1, i.e., for node 12. Then, we repeat this process until we are not on the leaf node. After reaching the leaf node, we process the leaf node, i.e., node 5. Next, we return to its parent, i.e., node 12. After processing the left subtree, we process the right subtree of 12 and repeat the same process as above. After that, we process node 12. 

Algorithm and Pseudocode of Postorder Tree Traversal

Algorithm:

Postorder(root)

• Traverse the left sub-tree, (call postorder(root_left).
• Traverse the right subtree, (call postorder(root_right).
• Visit the root node.

Pseudocode:

postorder(Node)

   if (Node != null)

       postorder(left_child)

       postorder(right_child)

       Process Node

  End if

End postorder

Applications of Postorder Tree Traversal

• Postorder traversal is used to delete the tree.
• Postorder traversal is also useful to get the postfix expression of an expression tree.

Levelorder Tree Traversal

Level-order traversal is another name of BFS to visit every node of a tree. 

In level-order traversal, we traverse the tree level-wise, which means we visit all nodes in the current level and then move on to the next level. We use a queue data structure to implement the level order traversal where we visit/process a node and then pop the current node from the queue and push its left and right child in the queue. 

This process continues till we process all the nodes in the tree.

Algorithm and Pseudocode for Level-order Tree Traversal

Algorithm:

Levelorder(node)

• Define an empty queue.
• Insert the starting node (root) into the queue.
• Pop the node from the queue and push all its children into the queue; repeat this process until the queue is not empty.
• Process the node popped in each iteration. 

Pseudocode:

levelorder(root)

   Queue q

   q.push(root)

   while ( ! q.empty() )

       Node = q.pop()

       Process Node

       q.push(left_child)

       q.push(right_child)

   End while

 End levelorder

Implementation of Tree Traversal: C++ Code 

Following code is an example of how you can implement tree traversal in C++: 

// Tree Traversals

#include <bits/stdc++.h>

using namespace std;

// Struct Node to represent the node of the tree

struct Node

{

    // data will store the value of the node

    int data;

    // left and right are the pointers to the left and right child of current node

    struct Node *left, *right;

    // constructor to initialise the variables

    Node(int data)

    {

        this->data = data;

        // initially left and right will be NULL

        left = right = NULL;

    }

};

// Recursive function to print the preorder traversal of the tree

void PreorderTraversal(struct Node *node)

{

    // base case if current node is NULL then we are done.

    if (node == NULL)

        return;

    // printing the data in current node

    cout << node->data << " ";

    // calling recursion for left child to visit that first

    PreorderTraversal(node->left);

    // calling recursion for right child

    PreorderTraversal(node->right);

}

// Recursive function to print the Postorder traversal of the tree

void PostorderTraversal(struct Node *node)

{

    // base case if current node is NULL then we are done.

    if (node == NULL)

        return;

    // calling recursion for left child

    PostorderTraversal(node->left);

    // calling recursion for right child

    PostorderTraversal(node->right);

    // printing the data in current node

    cout << node->data << " ";

}

// Recursive function to print the Inorder tree traversal of the tree

void InorderTraversal(struct Node *node)

{

    // base case if current node is NULL then we are done.

    if (node == NULL)

        return;

    // calling recursion for left child

    InorderTraversal(node->left);

    // printing the data in current node

    cout << node->data << " ";

    // calling recursion for right child

    InorderTraversal(node->right);

}

void LevelOrderTraversal(struct Node *node)

{

    // declaring the empty queue

    queue<Node *> q;

    // pushing the starting node in queue

    q.push(node);

    // loop till queue is not empty

    while (!q.empty())

    {

        Node *current = q.front();

        q.pop();

        // printing the data in current node

        cout << current->data << " ";

        // pushing the left and right childs provided they are not null

        if (current->left != NULL)

            q.push(current->left);

        if (current->right != NULL)

            q.push(current->right);

    }

}

int main()

{

    // creating the root node

    struct Node *root = new Node(4);

    // inserting the nodes in the tree

    root->left = new Node(2);

    root->right = new Node(6);

    root->left->left = new Node(1);

    root->right->left = new Node(5);

    root->left->right = new Node(3);

    root->right->right = new Node(7);

    // calling traversal functions

    cout << "Inorder tree traversal ";

    InorderTraversal(root);

    cout << "\n\n";

    cout << "Preorder tree traversal ";

    PreorderTraversal(root);

    cout << "\n\n";

    cout << "Postorder tree traversal ";

    PostorderTraversal(root);

    cout << "\n\n";

    cout << "Level order tree traversal ";

    LevelOrderTraversal(root);

    cout << "\n\n";

}

Output:

Inorder tree traversal 1 2 3 4 5 6 7

Preorder tree traversal 4 2 1 3 6 5 7

Postorder tree traversal 1 3 2 5 7 6 4

Level order tree traversal 4 2 6 1 3 5

Time and Space Complexity of Tree Traversal Algorithms

Time complexity: In all the traversals, we visit every node once. It takes O(1) time to visit a node; hence, the time complexity of all the traversals will be O(n). Thus, the time complexity is O(n) for all traversals. 

Auxiliary space: 

• For preorder, postorder, and inorder tree traversals: If we consider the recursion stack, the space required is O(h), where h is the tree’s height. Else, it is O(1).  
• For level-order traversal: Every node will be pushed in the queue exactly once. So, in the worst case, there can be O(n) nodes in the queue at a single moment. Hence, the space complexity is O(n).

Examples of Tech Interview Questions on Tree Traversals 

1. Print the bottom view of a binary tree
2. Convert a binary tree to its sum tree (in place)
3. Find whether a binary tree is a subtree of another binary tree
4. Find the distance between given pairs of nodes in a binary tree
5. Truncate a binary tree to remove nodes that lie on a path with sum less than “k”
6. Count all subtrees with the same value of nodes in a binary tree
7. Construct a binary tree in level-order and inorder tree traversal sequence
8. Set “next” pointer to the inorder tree traversal successor of all nodes in a binary tree
9. Find maximum path sum in a binary tree
10. Check if a given binary tree is a binary search tree or not
11. Find the vertical sum of a binary tree

Check out Interview Questions and Problems pages to learn more.

FAQs on Tree Traversals

Q1: How to apply any preorder, postorder, level-order, or inorder tree traversals to check whether the given binary tree is full or not?

A full binary tree is a tree having either zero or two children for each node. We can use any of the tree traversals: preorder, postorder, level-order, or inorder tree traversal. And while processing each node, we can check whether it has 0 or 2 children or not. This way, we can determine whether a given tree is a full binary tree or not. 

Q2: Can we do inorder tree traversal without recursion? 

Answer: Yes, we can do inorder tree traversal without recursion using the stack data structure. We create an empty stack, push the root node on it and then process the left subtree of the root node. To process the left subtree, we push the left child of the current node and update the current with its left child. We repeat this process until we are on the leaf node. Now, we pop the nodes one by one from the stack and process them, and update the current node with its right child. We repeat the same process until the stack is empty. Again, we follow the same process for the right subtree of the root node.

Pseudocode:

InorderTraversal

        Create Empty Stack

        While(true)

              If (root is not NULL)

                    Stack.push(root) 

                    root  = root.left_child

              End if              

              If (Stack if empty) 

                    Break the loop

              End if

              root  = Stack.pop()

              // process the node root             

              root  = root.right_child

      End while

End InorderTraversal

Q3: What is the use of inorder tree traversal? 

A variation of inorder tree traversal can be used to obtain nodes from BST in non-increasing order.

Q4: How do you do a tree traversal inorder?

We do a tree traversal inorder by traversing left, performing some operation on the current node, then traversing right.

Q5: What is true about doing tree traversal inorder?

Doing tree traversal inorder involves following the policy of Left-Root-Right.

Looking for a Tech Interview Prep Coach?

Interview Kickstart offers the best technical interview prep courses that make you a better engineer and help you nail tech interviews. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

For more information on what it takes to prepare for and succeed at FAANG tech interviews, sign up for our free webinar.