Binary Tree | the best 5 coding questions you must solve

In this article, we will see the top 5 most commonly asked interview problems on binary tree.

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

1. Size of the binary tree (i.e count of all nodes)
2. Height of the binary tree
3. The maximum node in the binary tree
4. The minimum node in the binary tree
5. Sum of all nodes in the binary tree

Problem 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 and medium for the latest articles.

It would encourage me to write more if you follow me here, I would really appreciate it.

Thank you for reading this, Let’s meet next time.