Data structures are one of the most important topics for any technical interview whether it be Amazon or Microsoft etc. Let’s see some of the Most Asked Binary Tree Interview Questions.
If we start by defining data structures then it can be understood as a way of organizing data. They are of two types:
- Linear data structures like arrays, linked lists, stacks, queues, etc
- Non-Linear data structures like Trees, Graphs, Tries, etc.
In a technical interview the most commonly asked tree questions are on Binary trees and Binary Search Trees and many times people find it hard to solve them. But don’t worry, in this article we’ve covered the most common and crucial questions you need to know to crack an interview.
First, we’ll start with a basic description of Binary trees and then further see the questions.
Binary Trees
Trees are multilevel data structures with hierarchical relations between their elements. Each tree has many nodes and every node has its own data or value, a left pointer pointing to the left subtree and a right pointer pointing to a right subtree.
A binary tree is a special type of tree that can have a maximum of 2 children. This means it can either have 0,1 or 2 children.
Theoretical Interview Questions on Binary Trees
The first interview round of companies is usually a technical interview where they ask 10-15 theoretical questions related to Data structures, DBMS, Concept of OOPS, etc. Here we have picked for you, the 11 most common questions companies ask on Binary Trees and they all have a one to two-liner answer.
Key Point: When in an interview try to be accurate and precise, telling big stories here won’t add up to extra points. Interviewers get less time to test you so the faster you answer the easier it will be for them to judge you.
Q1) What is a Root node?
It is the highest node in a tree that has no parent. For example, in above figure A is a root node.
Q2) What is Leaf Node?
Any node in a tree that has no child of its own is called a Leaf Node. For example, in the above figure D, E, F is leaf nodes.
Q3) What is a child Node?
In a tree, the node which is a descendant of any node is called a child node. For example, Figures, B and C are child nodes of A.
Q4) What is a parent Node?
A node that has a child is called the parent of that child node. For example, in above figure B is a parent node of D and E.
Q5) What is a full Binary Tree?
A Binary Tree is called a Full binary tree if every node of it has either 0 or 2 children only.
Q6) What is a complete Binary Tree?
A Binary Tree is called a Complete Binary Tree if all the levels are filled i.e., have 2 children except the last level where all keys are filled from the left side.
Q7) What is a Binary Search Tree?
A Binary Search Tree (BST) is a tree where every node follows two main properties.
- The value of the left child of the tree is less than the value of its parent node or the root node.
- The value of the right child of the tree is greater than the value of its parent node or the root node.
Q8) What is an AVL Tree?
It is a binary search tree in which the difference of the heights of the right and left subtrees of any node is either 0, 1, or -1.
Q9) What is a Red-Black Tree?
It is a self-balancing binary search tree in which every node has an extra bit that represents color: Red or Black. These bits/colors are used for determining that trees are balanced or not during deletion and insertion of nodes.
Q10) What is the maximum number of nodes in a binary tree with height ‘h’.
Maximum nodes = 2h+1 – 1
Q11) Height of perfect binary tree with n nodes.
Height: log2(n+1)-1
Top Coding Interview Questions on Binary Trees
The first interview round usually consists of 2-3 coding questions where the interviewer might ask you to share your screen and code or he/she might give you a platform of their own to code. In maximum cases, pseudo-codes work well as the interviewer is interested in knowing how you approach any question, your thought process behind it. But sometimes he also might ask you to run your code and show the desired output. In any case, be prepared.
Here we have picked for you the most common coding questions related to trees any interviewer asks in an interview.
Before the question, let’s just start by making a struct and class for a tree that will be used in our future codes. It is the basic structure of a tree.
Q1) Print the following Tree Traversals.
There are different tree traversal techniques
- Preorder Traversal
Algorithm
- Visit the root.
- Traverse the left subtree.
- Traverse the right subtree.
Code
| void Btree::preorder(Node *head){ if(head==NULL) return; cout<<head->data<<” “; preorder(head->left); preorder(head->right);} |
- Postorder Traversal
Algorithm
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root.
Code
| void Btree::postorder(Node *head){ if(head==NULL) return; postorder(head->left); postorder(head->right); cout<<head->data<<” “;} |
- Inorder Traversal
Algorithm
- Traverse the left subtree.
- Visit the root.
- Traverse the right subtree.
Code
| void Btree::inorder(Node *head){ if(head==NULL) return; inorder(head->left); cout<<head->data<<” “; inorder(head->right); } |
- Level Order Traversal
This is basically a Breadth First Search /BFS travel on a tree and is done with the help of queue.
| void Btree::levelorder(Node *head){ if(head==NULL) return; queue<Node*>q; q.push(head); while(!q.empty()) { int c=q.size(); for(int i=0;i<c;i++) { Node*t=q.front(); q.pop(); cout<<t->data<<” “; if(t->left) q.push(t->left); if(t->right) q.push(t->right); } c=0; } } |
- Spiral Order Traversal
This means Traversing the tree from the right to left then left to right and so on.
For example in the above tree: 10 20 30 70 60 50 40
| void Btree::spiralorder(Node *head){ if(head==NULL) return; queue<Node*>q; q.push(head); int level=0; while(!q.empty()) { int c=q.size(); vector<int>v; for(int i=0;i<c;i++) { Node*t=q.front(); q.pop(); v.push_back(t->data); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } if(level%2==0) reverse(v.begin(),v.end()); for(auto it:v) { cout<<it<<“–>”; } v.clear(); level++; }} |
Q2) Print the following views of a Binary Tree :
- Left View of a Tree
When the person will see the whole tree from the left side all the nodes visible to him/her from there will be the left view of that tree. For example in the above tree nodes
10 20 40 will be the left view of that tree. This method uses ques and is based on the level traversal of a tree. If we carefully observe the left view it’s nothing but the leftmost node of every level.
| void Btree::leftview(Node *head){ if(head==NULL) return; queue<Node*>q; q.push(head); while(!q.empty()) { int c=q.size(); for(int i=0;i<c;i++) { Node*t=q.front(); q.pop(); if(i==0) cout<<t->data<<” “; if(t->left) q.push(t->left); if(t->right) q.push(t->right); } c=0; }} |
- Right View of a Tree
This is similar to the Left view but here we have to print the last node of every level. For example, in the above tree nodes, 10 30 70 will be the right view of that tree.
| void Btree::rightview(Node *head){ if(head==NULL) return; queue<Node*>q; q.push(head); while(!q.empty()) { int c=q.size(); for(int i=0;i<c;i++) { Node*t=q.front(); q.pop(); if(i==c-1) cout<<t->data<<” “; if(t->left) q.push(t->left); if(t->right) q.push(t->right); } c=0; }} |
- Top View of a Tree
When the person will see the tree from the top only the top elements will be visible. For example, the top view of a Tree is 40 20 10 30 70.
To print the top view of trees we will imagine them to be on different y-axes and hence well print the topmost value on different axes.
We’ll start with the root node as 0 axes, to the right of this there will be +1,+2, and so on. Whereas to the left, it will be -1,-2, and so on.
Hence we will create a map<int,int>mp.
| void Btree::topview(Node*head,int hd,map<int,int>mp){ if(head==NULL) return; if(mp.count(hd)==0) { cout<<head->data<<“–>”; mp[hd]=head->data; } topview(head->left,hd-1,mp); topview(head->right,hd+1,mp);} |
- Bottom View of a Tree
It is similar to Top view of the tree just that here the bottom-most data of that axis is to be printed. The bottom view of the above tree is: 40 20 50 30 70
| void Btree::bottomview(Node *head,int hd,map<int,int>mp){ if(head==NULL) return; mp[hd]=head->data; bottomview(head->left,hd-1,mp); bottomview(head->right,hd+1,mp); } |
Q3) Find the height or maximum depth of a tree.
Algorithm
maxHeight()
- If tree is empty i.e. head==NULL return 0
- Using recursion, get the maximum length of the left subtree.
- Similarly, using recursion, get the maximum length of the right subtree.
- Get the maximum out of both left and right subtree heights and add 1.
- Return the maximum height.
| int Btree::height(Node *head){ if(head==NULL) return 0; int lh=height(head->left); int rh=height(head->right); return max(lh,rh)+1;} |
Q4) Find the diameter of the Tree.
The diameter of a tree is the count of nodes on the longest path or distance between any two end nodes.
| void Btree::di(Node *head){ if(head==NULL) return; int lh=height(head->left); int rh=height(head->right); res=max(res,lh+rh); } |
Q5) Find sum of all nodes in a Binary Tree.
For this, we can use any type of traversal to calculate the total sum of all nodes. Here I have shown using in order.
| void Btree::inorder(Node *head,int sum){ if(head==NULL) return; inorder(head->left,sum); sum+=head->data; inorder(head->right,sum); } |
Q6) Construct a Binary Search Tree from an array.
First of all sort the given array.
Algorithm
- Find the middle element of the array and make it a root of the tree.
- Using recursion do it for the left half as well as the right half.
a) Find the middle of the left half and make it as a left child of the root.
b) Find the middle of the right half and make it as a right child of the root.
Code
sort(a,a+n); //sort the given array // l->starting element of array// h->ending element of array// m->middle element of arrayVoid Btree::sortedArrayToBST(int a[],int l, int h){ if (l > h) return NULL; int m = (l+h)/2; Btree*root = newNode(a[m]); //making a new node root->left = sortedArrayToBST(a, l, m – 1); root->right = sortedArrayToBST(a, m + 1, h); return root;} |
Conclusion
In this article, we learned and saw some frequently asked questions on binary trees in interviews. The best advice for you all is to learn data structures by heart as they are most important for cracking technical interviews. Practicing the above-mentioned questions and coding them yourself will help you a lot. Initially, you might not see the results immediately but slowly with a lot of practice you will be easily able to crack any interview. Just be patient during any interview even if you get stuck at some question and don’t know how to code, do explain the question they usually judge you on your thinking process. All the best!!
