What are BFS and DFS for Binary Tree? A Tree is typically traversed in two ways:
BFS and DFSs of above Tree
Breadth First Traversal : 1 2 3 4 5 or 1 2 3 5 4 or 1 3 2 4 5 or 1 3 2 5 4
Depth First Traversals:
Preorder Traversal : 1 2 4 5 3
Inorder Traversal : 4 2 5 1 3
Postorder Traversal : 4 5 2 3 1
Why do we care? There are many tree questions that can be solved using any of the above four traversals. Examples of such questions are size, maximum, minimum, print left view, etc. Is there any difference in terms of Time Complexity? All four traversals require O(n) time as they visit every node exactly once. Is there any difference in terms of Extra Space? There is difference in terms of extra space required.
Maximum Width of a Binary Tree at depth (or height) h can be 2h where h starts from 0. So the maximum number of nodes can be at the last level. And worst case occurs when Binary Tree is a perfect Binary Tree with numbers of nodes like 1, 3, 7, 15, …etc. In worst case, value of 2h is Ceil(n/2). Height for a Balanced Binary Tree is O(Log n). Worst case occurs for skewed tree and worst case height becomes O(n). So in worst case extra space required is O(n) for both. But worst cases occur for different types of trees. It is evident from above points that extra space required for Level order traversal is likely to be more when tree is more balanced and extra space for Depth First Traversal is likely to be more when tree is less balanced. How to Pick One?
Exercise: Which traversal should be used to print leaves of Binary Tree and why? Which traversal should be used to print nodes at k’th level where k is much less than total number of levels? This Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!
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:
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.
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:
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.
Inorder(root)
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 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 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).
Preorder(root)
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 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.
Postorder(root)
postorder(Node)
if (Node != null)
postorder(left_child)
postorder(right_child)
Process Node
End if
End postorder
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.
Levelorder(node)
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 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 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:
Check out Interview Questions and Problems pages to learn more.
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.
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.
Comments
Please Join Us to post.
0