Hello guys, if you are preparing for coding interviews and want to master tree-based questions then you have come to the right place. A tree is one of the most important data structures because it allows you to store hierarchical data as opposed to an array and linked list which allows storing linear data. That's why knowledge of tree data structure is very important from an interview point of view. A lot of programmers and my readers have been asking me to share some binary tree-based coding interview questions, just like I have done for the array, linked list, string, software design, patterns, hash table, and data structure in general.
This task was actually pending for quite some time and it was stuck for me trying to find the solution for each and every question I could have collected. So, I decided to publish the list of binary tree interview questions now and possibly publish the solution as a separate article later.
This is like creating an interface and providing implementation later so that you don't block other people who are dependent upon your interface (actually, this is one advantage of using the interface in Java or any other programming language).
1) A tree is the hierarchical data structure unlike an array or linked list which are linear. This means you can store hierarchical information using a tree data structure, like an organization structure, family tree, etc.
2) A tree has nodes and children. The top or first node is called the root.
3) If you want to visualize, the tree data structure is like an inverted tree in the real world. I mean, when you see trees around you, their roots are in the bottom but when you draw a tree data structure in programming or computer science, their root is on top.
4) A binary tree is a special tree, where you can have at most two children. This means, one node can either have no child, one child, or two children. They cannot have three children or more.
5) All the nodes which don't have any children are known as leaf nodes.
6) Binary Search Tree is a special type of binary tree where values of the left subtrees are less than or equal to root and values of nodes on right subtrees are greater than or equal to root. This provides a sorting structure to a binary search tree, which makes searching really fast.
You can also check Data Structures and Algorithms: Deep Dive Using Java course on Udemy to learn more about binary search trees. It's one of the best courses to refresh your data structure and algorithms skills.
7) The binary search tree is closely associated with a binary search which works on the principle of reducing input size to half after every iteration. This makes the search really fast and you can find any element in the binary search tree on O(logN) time, but, only if the tree is balanced.
8) There are two ways to traverse a tree data structure, depth-first, or level first. At depth-first, you go down until there is no more node to visit and then you come back to visit nodes on the same level.
While in level order traversal, you visit all nodes at the same level before moving to the next level. There is also pre-order, post-order, and in-order traversal for binary which is used to traverse nodes of a binary tree. Inorder traversal is special because it visits all nodes in sorted order.
9) A balanced binary tree is like having an equal number of nodes on each subtree if you have all the nodes on the only left or right subtree then your binary tree will become un-balanced and it will act like a linked list as shown in the diagram below:
10) An unbalanced or non-balanced binary search tree acts like a linked list where a search will take O(n) time as opposed to O(logN) time in a balanced binary search tree.
These are some of the important points which every programmer should know about binary tree data structure. It will help you to solve tree-based coding problems. If you want to learn more about the binary tree and other data structures, I suggest you join a good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to brush your fundamentals.
To get the most from this list, try solving the problem before looking into a solution only then your mind will work and you will face challenges and consolidate your understanding. If you look at the solution immediately, you will only learn 10% but if you try you will learn 80 to 90% of the concepts and tricks behind each question.
1) How do you find the lowest common ancestor of a binary tree in Java? (solution)
2) How do you print the left view of a binary tree in Java? (solution)
3) Write a program to construct a tree from Inorder and PreOrder traversal in Java? (solution)
4) How do you print common nodes in two binary search trees in Java? (solution)
5) Why binary heap is a better choice over BST for implementing Priority Queue? (answer)
6) How do you check if a given binary tree is balanced or not? Write a Java method, which accepts a binary tree and returns true if it is balanced or false otherwise. (solution)
7) What are some advantages of a binary search tree over a hashtable data structure? (answer)
8) How do you check if a given binary tree is a subtree of another binary tree? (solution)
You have given two binary trees, and you need to return true if a first binary tree is a subtree of the second one. A subtree of binary tree BT is a tree T consisting of a node from BT and all of its descendants. For example, in the following case, T1 is a subtree of binary tree BT
9) How do you find the distance between two nodes in a binary tree? (solution)
10) How to find the lowest common ancestor in a binary tree in Java? (solution)
11) Write a Java program to check if all leaves of a given binary tree are at the same level? (solution)
12) How do you convert a given binary tree to doubly linked list in Java? (solution)
13) Write a program to find a depth of a given binary tree in Java? (solution)
14) What is the difference between binary and binary search trees? (answer)
15) What is a self-balanced tree? (answer)
16) What is the AVL Tree? (answer)
17) Write a Java program to print pre-order traversal of a binary search tree? Give a solution using both iteration and recursion? (solution)
18) Print the post-order traversal of BST? Give Iterative and recursive algorithm (solution)
19) Print the inorder traversal of a BST in Java? Give both Iterative and recursive algorithms (solution)
20) You have given a BST, where two nodes are swapped? How do you recover the original BST? (solution)
21) How do you convert a binary tree to a binary search tree in Java? (solution)
22) Find the largest BST subtree of a given binary tree in Java? (solution)
23) Write a Java program to connect nodes at the same level as a binary tree? (solution)
24) What is a Trie data structure? (answer)
25) What is the difference between the Binary tree and Trie? (answer)
26) Print ancestors of a given node of a binary tree in Java? (solution)
27) Write a Java program to print the level of a given node in a binary tree? (solution)
28) Print common nodes of two given BST in Java? (solution)
29) Give a binary tree, print all root-to-leaf paths in Java? (solution)
30) Print Inorder tree traversal without recursion in Java? (solution)
31) Print PreOrder tree traversal without recursion and stack in Java? (solution)
32) Print PostOrder tree traversal without recursion in Java? (solution)
33) Java Program to check if a given binary tree is BST or not? (solution)
34) Write a Java Program to count leaf nodes in a binary tree? (solution)
35) Write a Java program to find the height or depth of a binary tree? (solution)
36) How do you find if two given binary trees are the same? (solution)
Write a method in Java, which will accept two binary trees and return true if they are the same, otherwise return false.
37) How do you delete a given node from a binary search tree in Java? (solution)
38) Write a Java function to add a given node in a binary search tree? (solution)
39) Print a binary tree in vertical order in Java? (solution)
40) What is the Red-Black Tree data structure? (answer)
Answer - Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node has the following properties
a) Every node has a color, either red or black.
b) The root of the tree is always black.
c) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
d) Every path from the root to a NULL node has the same number of black nodes.
You can also check Data Structures in Java: An Interview Refresher course on Educative to learn more about Red Black Tree Data structure.
That's all in this list of top 40 binary trees and binary search tree-based coding problems from programming interviews. Although the solution is given in Java programming language, you are welcome to solve these questions on any programming language of your choice like Python, C, C++, JavaScript, Ruby, or even Swift. You can also post your solution in the comments section so that the community can review your solution and provide some useful feedback.
All the best for your coding interview.
Other Coding Interview Questions l you may like
Thanks for reading this article. If you like this article, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Data Structure and Algorithms courses on Udemy. It's authored by a Google Software Engineer and Algorithm expert, and it's completely free of cost.
What is Binary Tree Data Structure?
Anyway, coming back to a binary tree, I would like to re-iterate some of the useful points about tree data structure in general which will help you to solve these questions on your own:1) A tree is the hierarchical data structure unlike an array or linked list which are linear. This means you can store hierarchical information using a tree data structure, like an organization structure, family tree, etc.
2) A tree has nodes and children. The top or first node is called the root.
3) If you want to visualize, the tree data structure is like an inverted tree in the real world. I mean, when you see trees around you, their roots are in the bottom but when you draw a tree data structure in programming or computer science, their root is on top.
4) A binary tree is a special tree, where you can have at most two children. This means, one node can either have no child, one child, or two children. They cannot have three children or more.
5) All the nodes which don't have any children are known as leaf nodes.
6) Binary Search Tree is a special type of binary tree where values of the left subtrees are less than or equal to root and values of nodes on right subtrees are greater than or equal to root. This provides a sorting structure to a binary search tree, which makes searching really fast.
You can also check Data Structures and Algorithms: Deep Dive Using Java course on Udemy to learn more about binary search trees. It's one of the best courses to refresh your data structure and algorithms skills.
7) The binary search tree is closely associated with a binary search which works on the principle of reducing input size to half after every iteration. This makes the search really fast and you can find any element in the binary search tree on O(logN) time, but, only if the tree is balanced.
8) There are two ways to traverse a tree data structure, depth-first, or level first. At depth-first, you go down until there is no more node to visit and then you come back to visit nodes on the same level.
While in level order traversal, you visit all nodes at the same level before moving to the next level. There is also pre-order, post-order, and in-order traversal for binary which is used to traverse nodes of a binary tree. Inorder traversal is special because it visits all nodes in sorted order.
9) A balanced binary tree is like having an equal number of nodes on each subtree if you have all the nodes on the only left or right subtree then your binary tree will become un-balanced and it will act like a linked list as shown in the diagram below:
10) An unbalanced or non-balanced binary search tree acts like a linked list where a search will take O(n) time as opposed to O(logN) time in a balanced binary search tree.
These are some of the important points which every programmer should know about binary tree data structure. It will help you to solve tree-based coding problems. If you want to learn more about the binary tree and other data structures, I suggest you join a good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to brush your fundamentals.
40+ Binary Tree Interview Questions for Java Programmers
Without wasting any more of your time, here is my list of the binary tree and binary search tree (BST) based coding problems from Programming Job interviews. I have linked to solutions wherever is possible but if there is no link, you can also find a solution by just doing a Google search. They are very popular questions and many people have already solved them.To get the most from this list, try solving the problem before looking into a solution only then your mind will work and you will face challenges and consolidate your understanding. If you look at the solution immediately, you will only learn 10% but if you try you will learn 80 to 90% of the concepts and tricks behind each question.
1) How do you find the lowest common ancestor of a binary tree in Java? (solution)
2) How do you print the left view of a binary tree in Java? (solution)
3) Write a program to construct a tree from Inorder and PreOrder traversal in Java? (solution)
4) How do you print common nodes in two binary search trees in Java? (solution)
5) Why binary heap is a better choice over BST for implementing Priority Queue? (answer)
6) How do you check if a given binary tree is balanced or not? Write a Java method, which accepts a binary tree and returns true if it is balanced or false otherwise. (solution)
7) What are some advantages of a binary search tree over a hashtable data structure? (answer)
8) How do you check if a given binary tree is a subtree of another binary tree? (solution)
You have given two binary trees, and you need to return true if a first binary tree is a subtree of the second one. A subtree of binary tree BT is a tree T consisting of a node from BT and all of its descendants. For example, in the following case, T1 is a subtree of binary tree BT
9) How do you find the distance between two nodes in a binary tree? (solution)
10) How to find the lowest common ancestor in a binary tree in Java? (solution)
11) Write a Java program to check if all leaves of a given binary tree are at the same level? (solution)
12) How do you convert a given binary tree to doubly linked list in Java? (solution)
13) Write a program to find a depth of a given binary tree in Java? (solution)
14) What is the difference between binary and binary search trees? (answer)
15) What is a self-balanced tree? (answer)
16) What is the AVL Tree? (answer)
17) Write a Java program to print pre-order traversal of a binary search tree? Give a solution using both iteration and recursion? (solution)
18) Print the post-order traversal of BST? Give Iterative and recursive algorithm (solution)
19) Print the inorder traversal of a BST in Java? Give both Iterative and recursive algorithms (solution)
20) You have given a BST, where two nodes are swapped? How do you recover the original BST? (solution)
21) How do you convert a binary tree to a binary search tree in Java? (solution)
22) Find the largest BST subtree of a given binary tree in Java? (solution)
23) Write a Java program to connect nodes at the same level as a binary tree? (solution)
24) What is a Trie data structure? (answer)
25) What is the difference between the Binary tree and Trie? (answer)
26) Print ancestors of a given node of a binary tree in Java? (solution)
27) Write a Java program to print the level of a given node in a binary tree? (solution)
28) Print common nodes of two given BST in Java? (solution)
29) Give a binary tree, print all root-to-leaf paths in Java? (solution)
30) Print Inorder tree traversal without recursion in Java? (solution)
31) Print PreOrder tree traversal without recursion and stack in Java? (solution)
32) Print PostOrder tree traversal without recursion in Java? (solution)
33) Java Program to check if a given binary tree is BST or not? (solution)
34) Write a Java Program to count leaf nodes in a binary tree? (solution)
35) Write a Java program to find the height or depth of a binary tree? (solution)
36) How do you find if two given binary trees are the same? (solution)
Write a method in Java, which will accept two binary trees and return true if they are the same, otherwise return false.
37) How do you delete a given node from a binary search tree in Java? (solution)
38) Write a Java function to add a given node in a binary search tree? (solution)
39) Print a binary tree in vertical order in Java? (solution)
40) What is the Red-Black Tree data structure? (answer)
Answer - Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node has the following properties
a) Every node has a color, either red or black.
b) The root of the tree is always black.
c) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
d) Every path from the root to a NULL node has the same number of black nodes.
You can also check Data Structures in Java: An Interview Refresher course on Educative to learn more about Red Black Tree Data structure.
That's all in this list of top 40 binary trees and binary search tree-based coding problems from programming interviews. Although the solution is given in Java programming language, you are welcome to solve these questions on any programming language of your choice like Python, C, C++, JavaScript, Ruby, or even Swift. You can also post your solution in the comments section so that the community can review your solution and provide some useful feedback.
All the best for your coding interview.
Other Coding Interview Questions l you may like
- How to implement the insertion sort algorithm in Java? (tutorial)
- How to apply the Quicksort algorithm in place in Java? (tutorial)
- How to implement the Bubble sort algorithm in Java? (tutorial)
- Difference between Comparison and Non-Comparison based sorting algorithm? (answer)
- How to apply Bucket Sort in Java? (tutorial)
- How to implement Quicksort algorithm without recursion? (tutorial)
- How to perform a Binary Search Algorithm in Java? (tutorial)
- How to find all pairs in an array whose sum is equal to k (solution)
- How to remove duplicates from an array in Java? (solution)
- How to find the most significant and smallest number in an array without sorting? (solution)
- How to find duplicates from an unsorted array in Java? (solution)
- How to find one missing number in a sorted array? (solution)
- How to find a missing value from an array containing 1 to 100? (solution)
- 50+ Data Structure and Algorithms Problems from Interviews (questions)
- My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
- How to remove an element from an array in Java? (solution)
- How to check if an array contains a particular value? (solution)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)
- 100+ Data Structure Coding Problems from Interviews (questions)
Thanks for reading this article. If you like this article, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free Data Structure and Algorithms courses on Udemy. It's authored by a Google Software Engineer and Algorithm expert, and it's completely free of cost.
No comments:
Post a Comment
Feel free to comment, ask questions if you have any doubt.