Interview Kickstart has enabled over 3500 engineers to uplevel.

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 an important topic that will help you in your prep — tree 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

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 the 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.

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:

- Depth-First Search (DFS) Algorithms: Inorder, Preorder, and Postorder
- Breadth-First Search (BFS) Algorithms: Levelorder

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:

**Inorder:**Traverse left, perform some operation on the current node (in this article, we are printing the value stored in it), traverse right**Preorder:**Perform some operation on the current node, traverse left, traverse right**Postorder:**Traverse left, traverse right, Perform some operation on the current node

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

In inorder 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.

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.

**Algorithm:**

Inorder(root)

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

**Psuedocode:**

inorder(Node)

if (Node != null)

inorder(left_child)

Process the Node

inorder(right_child)

End if

End inorder

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 traversal prints the nodes in non-decreasing order. A variation of inorder traversal can be used to obtain nodes from BST in non-increasing order.

Preorder traversal is another variant of DFS, where operations in the recursive function are similar to inorder 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:**

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

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 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 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:**

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

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

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:**

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

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 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 traversal ";

InorderTraversal(root);

cout << "\n\n";

cout << "Preorder traversal ";

PreorderTraversal(root);

cout << "\n\n";

cout << "Postorder traversal ";

PostorderTraversal(root);

cout << "\n\n";

cout << "Level order traversal ";

LevelOrderTraversal(root);

cout << "\n\n";

}

**Output:**

Inorder traversal 1 2 3 4 5 6 7

Preorder traversal 4 2 1 3 6 5 7

Postorder traversal 1 3 2 5 7 6 4

Level order traversal 4 2 6 1 3 5 7

**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 inorder, preorder, and postorder 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).**

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

Check outInterview QuestionsandProblemspages to learn more.

**Question 1: How to apply tree traversals to check whether the given binary tree is full or not?**

Answer: A full binary tree is a tree having either zero or two children for each node. We can use any of the tree traversals, 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.

**Question 2: Can we do inorder traversal without recursion? **

Answer: Yes, we can do inorder 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

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.

------------

*Article contributed by Omkar Deshmukh*