Top 27 Binary Tree Interview Questions And Answers

Question 1

Define Binary Tree

Accepted Answer

A normal tree has no restrictions on the number of children each node can have. A **binary tree** is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.

There are three different types of binary trees:

* **Full binary tree**: Every node other than leaf nodes has 2 child nodes.
* **Complete binary tree**: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
* **Perfect binary tree**: All nodes have two children and all leaves are at the same level.

![](https://study.com/cimages/multimages/16/0e0646ba-30e5-40d9-b45c-a138f038f05b_full_complete_perfect.png)

Question 2

How is Binary Heap usually implemented?

Accepted Answer

A **binary heaps** are commonly implemented with an **array**. Any binary tree can be stored in an array, but because a binary heap is always a _complete_ binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices:

* The root element is `0`
* Left child : `(2*i)+1`
* Right child : `(2*i)+2`
* Parent child : `(i-1)/2`

![](https://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Binary_Heap_with_Array_Implementation.JPG/800px-Binary_Heap_with_Array_Implementation.JPG)

Question 3

What is Binary Search Tree?

Accepted Answer

**Binary search tree** is a data structure that quickly allows to maintain a _sorted list_ of numbers.

* It is called a _binary tree_ because each tree node has maximum of two children.
* It is called a _search tree_ because it can be used to search for the presence of a number in `O(log n)` time.

The properties that separates a binary search tree from a regular binary tree are:

* All nodes of left subtree are less than root node
* All nodes of right subtree are more than root node
* Both subtrees of each node are also BSTs i.e. they have the above two properties

![](https://cdn.programiz.com/sites/tutorial2program/files/bst-vs-not-bst.jpg)

Question 4

Implement _Pre-order Traversal_ of _Binary Tree_ using _Recursion_

Accepted Answer

For traversing a (non-empty) binary tree in pre-order fashion, we must do these three things for every node `N` starting from root node of the tree:

* (N) Process `N` itself.
* (L) Recursively traverse its _left_ subtree. When this step is finished we are back at N again.
* (R) Recursively traverse its _right_ subtree. When this step is finished we are back at N again.

![](https://www.techiedelight.com/wp-content/uploads/Preorder-Traversal.png)

Question 5

How to implement a _Tree_ data-structure? Provide some code.

Accepted Answer

That is a basic (generic) tree structure that can be used for `String` or any other object:

Question 6

What is Binary Heap?

Accepted Answer

A **Binary Heap** is a _Binary Tree_ with following properties:

* It’s a _complete_ tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
* A Binary Heap is either **Min Heap** or **Max Heap**. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

```js
            10                      10
         /      \               /       \  
       20        100          15         30  
      /                      /  \        /  \
    30                     40    50    100   40
```

Question 7

What is Balanced Tree and why is that important?

Accepted Answer

A tree is said to be balanced only when all three conditions satisfy:
* The left and right subtrees height differ by at most one
* The left subtree is balanced
* The right subtree is balanced

**Height-balancing** requirement:
* A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1. 
* A tree is height-balanced if all of its nodes are height-balanced.

![](https://www.afternerd.com/blog/wp-content/uploads/2018/03/balanced.jpg)

In a balanced BST, the height of the tree is `log n` where `n` is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto `n` which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time `O(n)` that shall be avoided.

> Balanced BST maintains `h` = `O(log n)` so all operations run in `O(log n)` time.

Question 8

Convert a Binary Tree to a Doubly Linked List

Accepted Answer

This can be achieved by traversing the tree in the **in-order** manner that is, left the `child -> root ->right` node.

![](https://www.techiedelight.com/wp-content/uploads/Inorder-Traversal.png)

In an in\-order traversal, first the left sub\-tree is traversed, then the root is visited, and finally the right sub\-tree is traversed.

One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list **in-place** i.e. we should not create new nodes for the doubly linked list.

This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.
*   Start with the root node and solve left and right sub\-trees recursively
*   At each step, once left and right sub\-trees have been processed:
    *   fuse output of left subtree with root to make the intermediate result
    *   fuse intermediate result (built in the previous step) with output from the right sub\-tree to make the final result of the current recursive call

Question 9

Name some ways to implement Priority Queue

Accepted Answer

**Priority Queue** abstract data type (ADT) can be implemented using other data structures (including Heaps) like:

* Unordered Array
* Unordered List
* Ordered Array
* Ordered List
* Binary Search Tree (BST)
* Balanced Binary Search Tree (AVL-tree)
* Binary heap

Compare the time efficiency of _heap implementation_ for main operations in Priority Queue ADT with other possible implementations:
```sh
----------------------------------------------------------------------------
| Implementation | Insertion   | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1           | n                            | n
----------------------------------------------------------------------------
| Unordered List | 1           | n                            | n
----------------------------------------------------------------------------
| Ordered Array  | n           | 1                            | 1
----------------------------------------------------------------------------
| Ordered List   | n           | 1                            | 1
----------------------------------------------------------------------------
| BST            | logn (avg.) | logn (avg.)                  | logn (avg.)
----------------------------------------------------------------------------
| Balanced BST   | log n       | log n                        | log n
----------------------------------------------------------------------------
| Binary Heaps   | log n       | log n                        | 1
```

Question 10

What are advantages and disadvantages of BST?

Accepted Answer

**Advantages of BST:**

* If we implement a balanced binary search tree, we can always keep the cost of `insert()`, `delete()`, `lookup()` to `O(log n)`
* BST is much faster than an array at search, insert, and delete (`O(log n)` vs `O(n)`)
* Code is simple relative to other data structures

**Disadvantages of BST:**

* BST is slightly slower than an array at access (`O(log n)` vs `O(1)`)
* A binary search tree can get out of balance (_imbalanced_) or become _degenerated_
* We should always implement a _balanced_ binary search tree (using some _self-balancing mechanism_) - AVL tree, Red-Black tree, Splay tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.

Top 27 Binary Tree Interview Questions

Define Binary Tree

How is Binary Heap usually implemented?

What is Binary Heap?

What is Binary Search Tree?

Name some ways to implement Priority Queue

Classify Tree Traversal Algorithms. Provide some visual explanation.

What is AVL Tree?

Explain the difference between Binary Tree and Binary Search Tree with an example?

What are advantages and disadvantages of BST?

What is Balanced Tree and why is that important?

Why do we want to use Binary Search Tree?

Explain how to balance AVL Tree?

What is Red-Black tree?

What is the time complexity for insert into Red-Black Tree?

What are main advantages of Tries over Binary Search Trees (BSTs)?

Explain what the main differences between red-black (RB) trees and AVL trees

Is there any reason anyone should use BSTs instead of AVLs in the first place?

How does inserting or deleting nodes affect a Red-Black tree?

What is the difference between Heap and Red-Black Tree?

How is an AVL tree different from a B-tree?

What's the main reason for choosing Red Black (RB) trees instead of AVL trees?

Implement Pre-order Traversal of Binary Tree using Recursion

How to implement a Tree data-structure? Provide some code.

Can you do Iterative Pre-order Traversal of a Binary Tree without Recursion?

Convert a Binary Tree to a Doubly Linked List

Build a Binary Expression Tree for this expression

What is Morris Traversal for a Tree and how to implement one?