In this article, We will see the top 5 most commonly asked interview problems on binary tree.
Hello WeekendTutorial Readers, I hope you and everyone around you are well and fine.
If you’re preparing for the job interviews for the position of software engineer/software developer or any role related to programming, you have to have a strong grasp of the data structures.
Non-linear data structures like Trees, Graphs are favorite topics from the interviewer’s point of view. This blog is about the binary tree data structure.
We have just started the interview problem series where we will see the top interview question that is asked in almost every interview. Along with the problems, we will also provide the solution in detail so that it can be clearer to you.
Note: If you have not read this, please do it first Binary Tree – How to implement using Javascript in 2022?
One strong suggestion though – Try the problems by yourself first. Once you’ve exhausted all the options and nothing working out only then check the solution. Believe me, practicing this will boost your confidence.
You will find that most of the time, you have almost reached the solution. Later this will be programmed in your mind and you’ll be able to find the approaches and reach the solution without any hint or help.
List of problems
- Size of the binary tree (i.e count of all nodes)
- Height of the binary tree
- The maximum node in the binary tree
- The minimum node in the binary tree
- Sum of all nodes in the binary tree
1. Size of the binary tree
The size of the binary tree is the total number of nodes present in the tree.
for example, the size of the below tree is 8
Size of tree = size of left subtree + size of right subtree + 1
function size(root) {
if (root === null) return 0;
return size(root.left) + size(root.right) + 1;
}
TC: O(N) ~ have to visit each node of the tree at most once
SC: O(N) ~ in case of skewed tree
2. Height of the binary tree
The height of the tree is the distance of the farthest leaf node from the root node of the tree.
for example, the height of the below tree is 4
Height of tree = Max(Height of left subtree, Height of right subtree) + 1
function height(root) {
if (root === null) return 0;
return Math.max(height(root.left), height(root.right)) + 1;
}
TC: O(N) ~ have to visit each node of the tree at most once
SC: O(N) ~ in case of skewed tree
3. The maximum node in the binary tree
The maximum node can be either root node or will be from the left or right subtree.
If we take the maximum of the above 3, the result will be the maximum node in the tree.
for example, the maximum of the below tree is 80
Largest node of tree = Max(
Largest in left subtree,
Largest in right subtree,
root.data
)
function largest(root) {
if (root === null) return 0;
return Math.max(
largest(root.left),
largest(root.right),
root.data
);
}
TC: O(N) ~ have to visit each node of the tree at most once
SC: O(N) ~ in case of skewed tree
4. The minimum node in the binary tree
The minimum node can be either root node or will be from the left or right subtree.
If we take the minimum of the above 3, the result will be the minimum node in the tree.
for example, the minimum of the below tree is 10
Smallest node of tree = Min(
Smallest in left subtree,
Smallest in right subtree,
root.data
)
function smallest(root) {
if (root === null) return 0;
return Math.min(
smallest(root.left),
smallest(root.right),
root.data
);
}
TC: O(N) ~ have to visit each node of the tree at most once
SC: O(N) ~ in case of skewed tree
5. Sum of all nodes in the binary tree
To sum all the nodes of the tree we need to visit each node using any tree traversal method. In this, I’m using postorder traversal.
for example, the maximum of the below tree is 360
sumTree = sumTree(left subtree) + sumTree(right subtree) + root.data
function sumTree(root) {
if (root === null) return 0;
return sumTree(root.left) + sumTree(root.right) + root.data;
}
TC: O(N) ~ have to visit each node of the tree at most once
SC: O(N) ~ in case of skewed tree
Summary
We have seen the most common problems that are asked in the interviews. We will come up with more problems that will cover the entire tree data structure.
Please stay along with the weekendTutorial for the latest articles.
I’m also on medium, it would be really appreciated if you follow me there.
Thank you for reading this, lets’s meet next time.
Please share the articles on –
The latest tips and news from the industry straight to your inbox!
Join 30,000+ subscribers for exclusive access to our monthly news and tutorials!
