Introduction to Binary Tree Interview Questions

Binary tree interview questions will consist of Top 10 most important questions which will be helpful to crack any data structure interviews. Binary tree being a data structure with each node having at most two child nodes, referred as left child node and right child node, and the first or top node referred as root node. There are few keywords to remember in Binary tree, i.e. Leaf node are the nodes which are at the bottom of the tree, which have no children. Each node in tree has a depth, meaning count of links from root node. Binary tree has height, which means count of links from root node to the last leaf node.

Top 10 Most Important Questions of Binary Tree

Binary tree interview questions are given below:

1. Define Binary Tree Data Structure?

Ans: Binary tree is a Hierarchical data structure, where tree has at most two children i.e., one node can have either no child nodes, one child node or two child nodes. Values of left subtree are less than or equal to root node and values of right subtree are greater than or equal to root node.

2. How to find out the distance between two nodes in binary tree?

Ans: Let us consider two nodes A and B that are part of Binary tree. Distance between Node A and Node B is equal to minimum number of edges that are required to be traversed from one node to another. NOTE: Shortest distance traversal is required in Binary tree

3. How To Find Lowest Common Ancestor (LCA) for Binary Tree?

Ans: Let us consider two nodes N1 and N2. Lowest Common Ancestor of N1 and N2 is the shared ancestor of N1 and N2 which is located farthest from root node

First, we need to find path from root node to N1 node and store in an array
Similarly, need to find path from root node to N2 node and store in an array
Then, traverse both paths until value is equal in both arrays.

4. How To Check if Two Binary Trees Are Identical or Not?

Ans: To check for identical structure and content, there are two approaches, Recursive approach and Iterative approach.

In Recursive, user needs to traverse both the trees and compare values at root node. If value matches, user needs to check if first tree’s left sub tree is identical to the left subtree of second binary tree and right sub tree of first binary tree is identical to the right subtree of second binary tree.
If value at root node is different, data property is violated.
If at any point, first tree is empty and second binary tree is non empty else if first tree is non empty and second tree is empty, structural property is violated.
In Iterative approach, stack data structure approach is used which is similar to implicit recursive approach.

5. What is AVL Tree?

Ans: AVL, named after Adelson-Velsky and Landis who are the inventors of AVL tree. AVL tree is a height balancing binary tree. It checks the height of left and right sub tree and assure the difference is not more than 1. This difference is called as Balancing factor.

BalanceFactor(N) = height(left sub tree(N)) – height(right sub tree(N))
N belongs to set { -1, 0, 1 }
If Balance factor N is more than 1, tree is balanced using,
Left Rotation, Right Rotation, Left Right Rotation, Right Right Rotation.

6. How is Traversing Done in Binary Tree?

Ans: Traversing refers to visiting all nodes of tree at least once. There are 3 ways in which traversing is done,

In order
Pre order
Post order

7. What is Binary Heap?

Ans: Binary Heap is Binary tree with below properties,

It is a complete tree i.e., all levels are completely filled except the last level and has all keys as left as possible. Property of Binary Heap makes suitable to be stored in array.
Binary Heap has two types, Min Heap and Max Heap.
In Min Heap, key at root node must be minimum amongst all keys present in Binary Heap. And this property must be true for all nodes in Binary tree. Max Heap is also similar to Min Heap.

8. How To Convert Binary Tree Into Binary Search Tree?

Ans: Main difference between Binary tree and Binary search tree is that binary search tree follows the left sub tree should have lower key value and right sub tree should have higher key value.

This can be achieved using below techniques,
First, we need to create temp array to store in order traversal of binary tree.
Then, sort temp array using any algorithm.
Repeat in order traversal.
Finally, copy array elements to each tree node.

9. How To Find Minimum and Maximum Element in Binary Tree?

Ans: As all the elements less than or equal to given root node will be to the left, iterating the left most part of the tree will give the least element in Binary tree.

Similarly, elements greater than or equal to given root node will be to the right, iterating the right most part of the tree will give the maximum element in Binary tree.

10. What Is the Average Time Complexity to Find Height of Binary Tree?

Ans: As the nodes are either part of left sub tree or right sub tree, user need not traverse through all nodes, which means complexity will be less than n. In average case, assuming nodes are spread evenly, time complexity will be O(logn)

Conclusion

With this we shall conclude with Binary tree interview questions. We have explored most of the important questions. Exploring more on logical part of Binary tree data structure will help to get better at programming too. You can try solving the concepts involved in Binary tree by changing values to build fundamentals.