Top Binary Tree Coding Interview Questions for Programmers

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.

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..

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.

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 Go? (solution)

2) How do you print the left view of a binary tree in Go? (solution)

3) Write a program to construct a tree from In-order and PreOrder traversal in Go? (solution)

4) How do you print common nodes in two binary search trees in Go? (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 Go 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 Go? (solution)

11) Write a Go 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 double linked list in Go? (solution)

13) Write a program to find a depth of a given binary tree in Go? (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 golang 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 Go? 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 Go? (solution)

22) Find the largest BST subtree of a given binary tree in Go? (solution)

23) Write a Go 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 Go? (solution)

27) Write a Go program to print the level of a given node in a binary tree? (solution)

28) Print common nodes of two given BST in Go or Python? (solution)

29) Give a binary tree, print all root-to-leaf paths in Go or Python? (solution)

30) Print Inorder tree traversal without recursion in Go or Python? (solution)

31) Print PreOrder tree traversal without recursion and stack in Go? (solution)

32) Print PostOrder tree traversal without recursion in Go? (solution)

33) Go Program to check if a given binary tree is BST or not? (solution)

34) Write a Go Program to count leaf nodes in a binary tree? (solution)

35) Write a Go 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 Go, 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 Go? (solution)

38) Write a Go function to add a given node in a binary search tree? (solution)

39) Print a binary tree in vertical order in Go? (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.

All the best for your coding interview.

Other Coding Interview Questions l you may like

  1. How to implement the insertion sort algorithm in Go? (tutorial)
  2. How to apply the Quicksort algorithm in place in Go? (tutorial)
  3. How to implement the Bubble sort algorithm in Go? (tutorial)
  4. Difference between Comparison and Non-Comparison based sorting algorithm? (answer)
  5. How to apply Bucket Sort in Go? (tutorial)
  6. How to implement Quicksort algorithm without recursion? (tutorial)
  7. How to perform a Binary Search Algorithm in Go? (tutorial)
  8. How to find all pairs in an array whose sum is equal to k (solution)
  9. How to remove duplicates from an array in Go? (solution)
  10. How to find the most significant and smallest number in an array without sorting? (solution)
  11. How to find duplicates from an unsorted array in Go? (solution)
  12. How to find one missing number in a sorted array? (solution)
  13. How to find a missing value from an array containing 1 to 100? (solution)
  14. How to remove an element from an array in Go? (solution)
  15. How to check if an array contains a particular value? (solution)

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.

Thank you Java67 for your  Notes.

Post a Comment