Home » Algorithm » Binary Search Tree » Binary Tree » Datastructure » Interviews » Top Binary Tree Interview Questions.

Top Binary Tree Interview Questions.

in , , , , - on 22:52:00 - No comments

Binary Tree Interview Questions.

Binary tree questions is very common during interviews. In this post we will focus on Top Binary tree and Binary Search tree interview questions and answers. 


In this post we will look at,
1. Basic Interview Questions on Binary Tree.
2. Most commonly asked Interview Questions on Binary Tree.

Basic Interview Questions on Binary Tree.
Question 1: What are the types of Binary tree?
Answer: 
Types of Binary Tree in Data Structure. Let's see Binary Tree types with example. There are mainly 3 types of Binary trees.

  1. Full binary tree / Proper binary tree / 2-tree / Strictly binary tree) 
  2. Perfect Binary Tree. 
  3. Complete Binary Tree:
Full binary tree / Proper binary tree / 2-tree / Strictly binary tree)
Full Binary Tree is a tree in which every node except leaves/leaf node has either 0 or 2 children.
There will be no leaves with only 1 child.
 
Example of Full Binary Tree:  More ...

Question 2:
Explain Binary tree Traversals with example?
Answer:
There are 2 types of Graph traversal algorithms Breadth first traversal and Depth First traversal. 
Tree is a special kind of Graph in which Breadth first traversal and Depth First traversal is divided as follows,
  1. Breadth First Traversal.
    • Level Order Traversal 
  2. Depth First Traversal
    • Preorder traversal
    • Inorder traversal
    • Postorder traversal
Breadth First Traversal
Breadth First Traversal is a traversing way where child at same levels are read first before visiting their child. which is nothing but a LEVEL-ORDER Traversal. More....

Question 3:
How to add a Node in Binary Tree?
Answer:
To add a Node in a Binary Tree, Start scanning a Binary Tree level by level and wherever we encounter vacant position, place a new Node there.

See below image to get better understanding of position of a new Node to insert.
Given a binary tree, we need to add a Node with value 8 marked in dotted lines below in its correct position. 
Java Program to Insert Node in Bina More....

Question 4:
How to add a Node in Binary Search Tree?
Answer:
While adding a Node in a Binary Search Tree, it should follow below rules,
  1. All values descending on the Left side of a node should be less than (or equal to) the node itself.
  2. All values descending on the Right side of a node should be greater than (or equal to) the node itself.

Java Program to Insert Node in Bina More....
Question 5:
How to Delete a node in Binary Search Tree?
Answer:
There are 3 cases that need to be considered while deleting a node from Binary Search Tree.
  1. Node to delete has no children that is no left child and no right child present. Case 1 in below image.
  2. Node to delete has only one child either left child or right child present. Case 2 in below image. 
  3. Node to delete has both child that is left child and right child present. Case 3 in below image.
 Case 1:
    For case 1, it is very much straightforward,
    1. Search for the node that need to be deleted. More....



Frequently Asked Interview Questions on Binary Tree.
Question 6:
Check if Two Binary Trees are identical?
Answer:
Two Binary Trees are considered equal if they are structurally identical and the nodes have the same value.

See below image for better understanding of which Trees are called Identical and which not.
More...

Question 7:
Check a given two Binary Trees are Mirror Image of each other?
Answer:
Two Binary Trees are considered mirror image of each other if there left and right child of every node is inter-exchange. (Left child moved to Right and Right chile moved to Left)

See below image for better understanding of which Trees are called Mirror Image of each other
Question 8:
Connect nodes at same level in a Binary Tree?
Answer:
Let us first understand what we want to achieve? what is the input and what will be the expected output.

 Binary Tree is given to you,
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and 
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null.
Our task is to connect nextRight pointer of each node to its adjacent node.   

1. If the immediate adjacent node is not present then connect to next adjacent node and
2. If next adjacent node is not present then connect to next to next adjacent node and
3. If next to next adjacent node is not present then search until you find the adjacent node along
    the same Level and connect to it.
4. If the adjacent node is not present at same level then connect it to null. 

Question 9:
Connect nodes at same level in a Binary Tree using constant extra space?
Answer:
This problem is variation of above question number 8. you can see details of this post on this link.
Connect nodes at same level in a binary tree using constant extra space.

Question 10:
Construct a Binary Tree from In-order and Level-order traversals?
Answer:
Two traversals are given as input,
   
int[] inOrder =    { 4, 2, 6, 5, 7, 1, 3 };
int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

By using above two given In order and Level Order traversal, construct Binary Tree like shown below More...

Question 11:
Construct a Binary Tree from In-order and Pre-order traversals?
Answer:
Two traversals are given as input,
   
int inorder[] =  {20, 30, 35, 40, 45, 50, 55, 60, 70};
int preorder[] = {50, 40, 30, 20, 35, 45, 60, 55, 70};
 
By using above 2 given In order and Pre Order traversal, construct Binary Tree like shown below,
More...

Question 12:
Zig Zag or Spiral Traversal of Binary Tree?
Answer:
Given a binary tree, write a program to print nodes of the tree in spiral order. 
You can also say it as Spiral order traversal of a tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?

If you observe Zig Zag Traversing is very similar to Level order traversal with few modification.
More... 

Question 13:
Boundary Traversal of Binary Tree?
Answer:
We have to print the boundary nodes of given Binary Tree in anti-clockwise starting from the root.
  1. Print Left boundary Nodes. 
  2. Print Leaf Nodes. 
  3. Print Right boundary Nodes in Bottom up fashion.
Let's take an example and try to understand. For reference we will More...

Question 14:
Print a Binary Tree in Vertical Order?
Answer:
Given a binary tree, print it vertically.

Vertical order Traversal of a tree is little bit different than Pre order, Post order, In order and Level order traversal.

We need to identify, which node will be part of Line 1, Line 2, Line 3 and so on, How to do that? If you observe, then there is a close relation between each line from root. More...

Question 15:
Print Nodes in Top View of Binary Tree?
Answer:
Given a binary tree, print the nodes that is visible, when the tree is viewed from the top.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Top view means, when we look the tree from the top, the nodes that are visible will be called the top view of the tree. So in the above image,

Solution: "If two nodes have the same Horizontal Distance from root, then they are on same vertical line." Lets understand this line in more detail. More...


Question 16:
Print Nodes in Bottom View of Binary Tree?
Answer:
Given a binary tree, print the nodes that is visible, when the tree is viewed from the bottom.

Let us first understand what we want to achieve? what is the input and what will be the expected output?

Bottom view means, when we look the tree from the bottom, the nodes that are visible will be called the bottom view of the tree. So in the above image,

Solution for printing the nodes visible from bottom view of binary tree is very similar to vertical traversal of binary tree. More...


Question 17:
Find Kth smallest element in BST(Binary Search Tree)?
Answer:
Solution is very simple:
  1. Take a variable counter, which keep track of number of smallest element read till now. 
  2. Do In order traversal, instead of printing the node in in-order traversal, increment the counter till it matches K. 
  3. Check whether counter value is equal to K. 
  4. If YES, then current node is Kth smallest node and return it. If NO, then return -1 as indication that given 'K' is invalid. More...

Question 18:
Find Kth largest element in BST(Binary Search Tree)?
Answer:
Solution is very simple:
  1. Take a variable counter, which keep track of number of largest element read till now.
  2. Do In-order traversal starting from right side (Right to Left instead of Left to Right), instead of printing the node in in-order traversal, increment the counter till it matches K.
  3. Check whether counter value is equal to K.
  4. If YES, then current node is Kth largest node and return it. If NO, then return -1 as indication that given 'K' is invalid.. More...

Question 19:
Find diameter of Binary Tree.?
Answer:
A longest path or route between any two nodes in a tree is called as Diameter/Width of binary tree.

The diameter of tree may or may not pass through the root.
The diagram below shows two trees each with diameter 7, diameter are shaded with blue nodes.
We will discuss 3 solutions,

  1. By using Global variable.
  2. By computing height and diameter of each node.
  3. By computing height and diameter of each node in optimized way. More...

Question 20:
Given an array of numbers, verify whether it is the correct Preorder traversal sequence of a binary search tree?
Answer:
You are given an array of numbers which represents Preorder traversal of Binary Search Tree.
Verify whether it is a correct Preorder sequence or not.

Lets understand what is the input and the expected output.

Input: [40, 30, 35, 20, 80, 100]
Output: Invalid Preorder traversal

Input: [45, 25, 15, 35, 75]
Output: Valid Preorder traversal

Input: [50, 39, 44, 28, 85]
Output: Invalid Preorder traversal. More..


Question 21:
Construct a Binary Tree from In-order and Post-order traversals
Answer:
Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question: Two traversals are given as input,
  
int inOrder[] =   {20, 30, 35, 40, 45, 50, 55, 60, 70};
int postOrder[] = {20, 35, 30, 45, 40, 55, 70, 60, 50};
By using above 2 given In order and Post Order traversal, construct Binary Tree More..
  
Question 22:
Serialize and Deserialize a Binary Tree.
Answer:
Design an algorithm to serialize and deserialize given Binary Tree. Serialization is to store tree in a File/String, so that it can be later restored. Deserialization is reading tree back from file.Serialization:
For Serialization process, we can read the given Binary Tree in any order and create a String representation of tree as long as same String is capable of converting back to same given Binary Tree.
    
Question 23:
Convert Sorted Array to Balanced Binary Search Tree(BST).
Answer:
Given a sorted array, create a Balanced Binary Search Tree using array elements.
A Binary Search Tree is called Balanced if, the height of left subtree and height of right subtree of Root differ by atmost 1.

We are given a sorted array, So which element we will pick as a Root Node for our BST such that it will be balanced.
If we pick the middle element of the array as Root node and distribute the left portion More..

    
Question 24:
Convert Sorted Linked List to balanced BST.
Answer:
Given a singly Linked List where elements are sorted in ascending orderconvert it to a height balanced BST.

A Binary Search Tree is called balanced if the height of left subtree and height of right subtree of Root differ by at most 1.

Lets understand the problem statement graphically and it will be more clear, More..
Question 25:
Print Nodes at K distance from Root in Binary Tree.
Answer:
Given a Binary Tree, Print all Nodes that are at K distance from root node in Binary Tree.
We can also think of this question as Print all nodes that belong to Level K.

Lets understand what will be input and expected output with the help of an example. More..
Question 26:
Print nodes at K distance from Leaf node in Binary tree.
Answer:
Given a Binary Tree, Print all Nodes that are at K distance from leaf node in Binary Tree.
Lets understand what will be input and expected output with the help of an example.

If k = 1. It means we need to print all nodes that are at distance 1 from Leaf node.

In Case 2, we have 4 leaf nodes (Node 1, Node 10, Node 5, Node7).
Node at distance K that is Node at distance 1 from leaf Node 1 is Node 2 (Print 2)
Node at distance K that is Node at distance 1 from leaf Node 10 is Node 9 (Print 9)
Node at distance K that is Node at distance 1 from leaf Node 5 is Node 6 (Print 6)
Node at distance K that is Node at distance 1 from leaf Node 7 is Node 6 (6 already printed, ignore)
Question 27:
Get Level/Height of node in binary tree.
Answer:
Given a binary tree, you need to find the height of a given node in the tree. Finding level of node of binary tree is equivalent to finding Height of node of binary tree.

There are 2 approach to find level of node in binary tree,
  1. Recursive approach. 
  2. Iterative approach. More..
 

Question 28:
Check if two nodes are cousins in a Binary Tree.
Answer:
Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not.

Two nodes are cousins if,
  1. They are not siblings (Children of same parent).  
  2. They are on the same level.
Two nodes are cousins of each other if they are at same level and have different parents. More..

 

Question 29:
Check whether Binary Tree is foldable or not.
Answer:
Check whether given binary tree can be folded or not. Binary Tree is said to be Foldable if nodes of Left and Right Subtree are exact mirror of each other.

  1. Traverse Binary Tree and compare left node of Left subtree with right node of Right subtree. 
  2. Traverse Binary Tree and compare right node of Left subtree with left node of Right subtree. 
  3. In both steps 1 and 2 above, check both left and right node is null or both left and right node is not null, if Yes, then Tree is foldable and has identitical structure otherwise not. More..

 You may also like to see

Top 10 Matrix Interview Questions in Java

What is Hashmap data structure? What is the need of Hashmap? 

What is Hashcode? Can 2 objects have same hashcode?

How time complexity of Hashmap get() and put() operation is O(1)? Is it O(1) in any condition?

What is Load factor and Rehashing in Hashmap?

Advanced Multithreading Interview Questions In Java 

How ConcurrentHashMap works and ConcurrentHashMap interview questions

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Categories: , , , ,

Post a Comment