Binary Tree Interview Questions and Answers

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.

Problem

Given a binary tree, return the preorder traversal of its nodes' values. Can you do it without recursion?

Solution

Let's use Stack:

1. Set current node as root
2. Check if current node is null then return
3. Store current node value in the container
4. Put right on stack
5. Put left on stack
6. While stack is not empty i. pop from stack into current node. Note, the left will be on top of stack, and will be taken first ii. Repeat from step 2 Implementation: CS

/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
  if (root == null) {
    return new ArrayList<>();
  }
List<Integer> rst = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
  TreeNode node = stack.pop();
  rst.add(node.val);
  if (node.right != null) {
    stack.push(node.right);
  }
if (node.left != null) {
  stack.push(node.left);
}
}
return rst;
}

PY
def preorder_iterative(root, result):
'''

Pre-order iterative traversal. The nodes' values are appended to the result list in traversal order ''' if not root: return

stack = []
stack.append(root)
while stack:
node = stack.pop()
result.append(node.value)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)

Tree Traversal algorithms can be classified broadly in two categories:

Depth-First Search (DFS) Algorithms
Breadth-First Search (BFS) Algorithms
Depth-First Search (DFS) Algorithms have three variants:
1. Preorder Traversal (current-left-right)— Visit the current node before visiting any nodes inside left or right
subtrees.
2. Inorder Traversal (left-current-right)— Visit the current node after visiting all nodes inside left subtree but

before visiting any node within the right subtree. 3. Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of left and right subtrees.

Breadth-First Search (BFS) Algorithm has one variant:

1. Level Order Traversal — Visit nodes level-by-level and left-to-right fashion at the same level.

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:

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

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

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 Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n)

Recursive solution has

O(
h) memory complexity as it will consume memory on the stack up to the height of

binary tree h . It will be

O(
log n) for balanced tree and in worst case can be
O(
n) .
Implementation:
Java
public static void BinaryTreeToDLL(Node root) {
  if (root == null)
  return;
  BinaryTreeToDLL(root.left);
  if (prev == null) {
    // first node in list
    head = root;
  } else {
    prev.right = root;
    root.left = prev;
  }
prev = root;
BinaryTreeToDLL(root.right);
if (prev.right == null) {
  // last node in list
  head.left = prev;
  prev.right = head;
}
}
PY
def BinaryTreeToDLL(self, node):
#Checks whether node is None
if(node == None):
return;#Convert left subtree to doubly linked list
self.BinaryTreeToDLL(node.left);#If list is empty, add node as head of the list
if(self.head == None):

#Both head and tail will point to node

self.head = self.tail = node;

#Otherwise, add node to the end of the list else: #node will be added after tail such that tail's right will point to node

self.tail.right = node;
#node's left will point to tail
node.left = self.tail;
#node will become new tail
self.tail = node;#Convert right subtree to doubly linked list
self.BinaryTreeToDLL(node.right);

AVL trees are height balancing binary search tree. It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. This allows us to search for an element in the AVL tree in O(log n) , where n is the number of elements in the tree.

The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N))
// BalanceFactor(N) belongs to the
set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations: Left Rotation, Right Rotation, Left Right Rotation, Right Left Rotation.

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

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.

If we implement a balanced binary search tree, we can always keep the cost of insert() , delete() , lookup() to O(log n) where n is the number of nodes in the tree - so the benefit really is that lookups can be done in logarithmic time which matters a lot when n is large. This is much better than the

linear time O(n)
required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash
tables.

Binary tree: Tree where each node has up to two leaves 1 /
2 3 Binary Search Tree (BST): Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent. 2 /
1 3

The major difference between a binary heap and a red-black tree is the performance on certain operations: Heap Pros It makes an ideal priority queue, since the min/max element (depending on your implementation) is always O(1) access time, so no need to search for it. It's also very fast for insertion of new values - O(1) on average, O(log n) worst case. Heap Cons Slow searches O(n) for random elements. RB Tree Pros Better searching O(log n) and good insertion O(log n) performance. RB Tree Cons Slower min/max searches. More overhead in general.

if you want to compare AVL tree with simple binary search tree (BST) without balancing, then AVL: will consume more memory (each node has to remember its balance factor) and each operation can be slower (because you need to maintain the balance factor and sometimes perform rotations). BST without balancing has a very bad (linear) worst case. But if you know that this worst case won't happen to you, or if you're okay if the operation is slow in rare cases, BST without balancing might be better than AVL.

The major difference between a binary heap and a red-black tree is the performance on certain operations: Heap Pros It makes an ideal priority queue, since the min/max element (depending on your implementation) is always O(1) access time, so no need to search for it. It's also very fast for insertion of new values - O(1) on average, O(log n) worst case. Heap Cons Slow searches O(n) for random elements. RB Tree Pros Better searching O(log n) and good insertion O(log n) performance. RB Tree Cons Slower min/max searches. More overhead in general.

To ensure that its color scheme and properties don’t get thrown off, red-black trees employ a key operation known as rotation. Rotation is a binary operation, between a parent node and one of its children, that swaps nodes and modifys their pointers while preserving the inorder traversal of the tree (so that elements are still sorted). There are two types of rotations: left rotation and right rotation. Left rotation swaps the parent node with its right child, while Right rotation swaps the parent node with its left child.

For small data: insert: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation. lookup: AVL tree is faster, because AVL tree has less depth. delete: RB tree has constant number of max rotation but AVL tree can have

O(
log n) times of rotation as

worst. and on average RB tree also has less number of rotation thus RB tree is faster.

For large data: insert: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to

O(
log n) . but AVL tree

& RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node. lookup: AVL tree is faster. (same as in small data case) delete: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation. In overall AVL trees maintain a more rigid balance than red-black trees. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2) , while in red black trees it's at most ~2 lg (n+1) . As a result, lookup in an AVL tree is typically faster, but this comes at the cost of slower insertion and deletion due to more rotation operations. So use an AVL tree if you expect the number of lookups to dominate the number of updates to the tree.

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1. The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N))
// BalanceFactor(N) belongs to the
set {-1,0,1}
If the balance factor

of a tree doesn’t equal -1,0, or 1 then our tree is unbalanced: BalanceFactor = height(left_sutree) − height(right_sutree)

// BalanceFactor not in {-1,0,1} => UNBALANCED
and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one

or more of 4 tree rotations: Single Rotations:

Left Left Rotation Right-Right Rotation, Double Rotation: Left Right Rotation or Double Left, Right Left Rotation or Double Right. Now, we say that a sub-tree is: left-heavy if the balance factor is greater than zero (> 0) right-heavy if the balance factor is lesser than zero (< 0) How we determine which rotation to use follows a few basic rules. See psuedo code:

IF tree is left heavy {
  IF tree 's left subtree is right heavy {
    Perform Double Right rotation
    /*
    c b
    / / \
    a == 2R ==> a c
    \
    b
    */
  }
ELSE { // Left Left case
  Perform Single Right rotation
  /*
  c b
  / / \
  b == 1R ==> a c
  /
  a
  */
}
}
IF tree is right heavy {
  IF tree 's right subtree is left heavy {

    Perform Double Left rotation
    /*
    a b
    \ / \
    c == 2L ==> a c
    /
    b
    */
  }
ELSE { // Right Right Case
  Perform Single Left rotation
  /*
  a b
  \ / \
  b == 1L ==> a c
  \
  c
  */
}
}

A red-black tree is a binary search tree in which each node has a color (red or black) associated with it (in addition to its key and left and right children). This can be saved in memory as a single bit (e.g. 'red' = 1, 'black' = 0). the following 3 properties hold: (root property) The root of the red-black tree is black (red property) The children of a red node are black. (black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same. This is sometimes known as the black-depth. The height of the red-black tree is at most 2*log(n + 1) Red-black trees maintain a slightly looser height invariant than AVL trees. Because the height of the red-black tree is slightly larger, lookup will be slower in a red-black tree. However, the looser height invariant makes insertion and deletion faster. Also, red-black trees are popular due to the relative ease of implementation.

Inserting a key into a non-empty tree has three steps. In the first step, the BST insert operation is performed. The BST insert operation is O (height of tree) which is O(log n) because a red-black tree is balanced. The second step is to color the new node red. This step is O(1) since it just requires setting the value of one node's color field. In the third step, we restore any violated red-black properties. Restructuring is O(1) since it involves changing at most five pointers to tree nodes. Once a restructuring is done, the insert algorithm is done, so at most 1 restructuring is done in step 3. So, in the worst-case, the restructuring that is done during insert is O(1) . Changing the colors of nodes during recoloring is O(1) . However, we might then need to handle a double-red situation further up the path from the added node to the root. In the worst-case, we end up fixing a double-red situation along the entire path from the added node to the root. So, in the worst-case, the recoloring that is done during insert is O(log N) ( = time for one recoloring * max number of recolorings done = O(1) * O(log N) ). Thus, the third step (restoration of red-black properties) is O(log N) and the total time for insert is O(log N) .

Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n)

The following are the main advantages of tries over binary search trees (BSTs): Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. A BST performs O(log n) comparisons of keys, where n is the number of elements in the tree, because lookups depend on the depth of the tree, which is logarithmic in the number of keys if the tree is balanced. Hence in the worst case, a BST takes O(m log n) time. Moreover, in the worst case log(n) will approach m . Also, the simple operations tries use during lookup, such as array indexing using a character, are fast on real machines. Tries are more space efficient when they contain a large number of short keys, because nodes are shared between keys with common initial subsequences. Tries facilitate longest-prefix matching, helping to find the key sharing the longest possible prefix of characters all unique.

The number of internal nodes from root to leaf equals the length of the key. Balancing the tree is therefore no concern.

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. 10 10 / \ /
20 100 15 30 / / \ /
30 40 50 100 40

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

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

public class Tree<T> {
  private Node<T> root;
  public Tree(T rootData) {
    root = new Node<T>();
    root.data = rootData;
    root.children = new ArrayList<Node<T>>();
  }
public static class Node<T> {
  private T data;
  private Node<T> parent;
  private List<Node<T>> children;
}
}
PY
Generic Tree:
class Tree(object):
"Generic tree node."
def __init__(self, name='root', children=None):
self.name = name
self.children = []
if children is not None:
for child in children:
self.add_child(child)
def __repr__(self):

return self.name def add_child(self, node):

assert isinstance(node, Tree)
self.children.append(node)
# *
# /|\
# 1 2 +
# / \
# 3 4
t = Tree('*', [Tree('1'),
Tree('2'),
Tree('+', [Tree('3'),
Tree('4')])])
Binary tree:
class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None

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

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. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Implementation: Java

// Recursive function to perform pre-order traversal of the tree
public static void preorder(TreeNode root)

{
  // return if the current node is empty
  if (root == null) {
    return;
  }// Display the data part of the root (or current node)
System.out.print(root.data + " ");// Traverse the left subtree
preorder(root.left);// Traverse the right subtree
preorder(root.right);
}
PY
# Recursive function to perform pre-order traversal of the tree
def preorder(root):# return if the current node is empty
if root is None:

return# Display the data part of the root (or current node)

print(root.data, end=' ')# Traverse the left subtree
preorder(root.left)# Traverse the right subtree
preorder(root.right)

Red-black trees are more general purpose. Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(log n) time. However, there are following points of comparison between the two:

AVL trees are more rigidly balanced and hence provide faster look-ups. Thus for a look-up intensive task use an AVL tree. For an insert intensive tasks, use a Red-Black tree. RB-Trees guarantee O(1) rotations per insert operation AVL trees store the balance factor at each node. This takes O(n) extra space. However, if we know that the keys that will be inserted in the tree will always be greater than zero, we can use the sign bit of the keys to store the colour information of a red-black tree. Thus, in such cases red-black tree takes no extra space. RB Trees do relatively well on: add, remove, and look-up AVL trees have: faster look-ups (AVL tree is, usually, has better balance ~1.44 log(N) than RB-tree 2 log(N) ) at the cost of slower add/remove.

Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This "shortness" allows searching to be performed inO( log n) time, because the largest possible number of reads corresponds to the height of the tree. But: An AVL tree is a self-balancing binary search tree. AVL trees are intended for in-memory use, where random access is relatively cheap. AVL trees are not designed to hold massive collections of data, as they use dynamic memory allocation and pointers to the next block of memory. A B-tree is a balanced tree, but it is not a binary tree )rather it's multi-way tree (N-ary tree)). B-Trees are better suited for disk-backed storage. A B-tree holds many children at one node and many pointers to children node. This way, during a disk read (which can take around 10 ms to read a single disk block), the maximum amount of relevant node data is returned, as well as pointers to "leaf node" disk blocks. This allows retrieval time of data to be amortized to log(n) time, making the B-tree especially useful for database and large dataset retrieval implementations.

Morris (In-Order) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree. Basically a tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node. Consider:

C E H A D I B G F Algorithm: Initialize the root as the current node curr . While curr is not NULL , check if curr has a left child. If curr does not have a left child, print curr and update it to point to the node on the right of curr . Else, make curr the right child of the rightmost node in curr 's left subtree. Update curr to this left node. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) The way of looking at time complexity is to find out how many times a tree node will be traversed. As it is constant (3 times for a binary tree). So we are looking at O(n) . Implementation: Java

public class MorrisPreorderTraversal {
  static class Node {
    //static class to represent node structure
    int data;
    //to store data of each node
    Node left, right;
    //to point to left and right child of the node respectively
    Node(int d) {
      //constructor for initialisation of each values
      this.data = d;
      this.left = null;
      this.right = null;
    }
}
public static void printPreorder(Node root) {
  if (root == null) {
    //if tree is empty
    return;

  }
while (root != null) {
  if (root.left == null) {
    //if left child is empty
    System.out.print(root.data + " ");
    //traverse current node and
    root = root.right;
    //move to it's right
  } else {
    Node curr = root.left;
    //to store inorder predecessor
    while (curr.right != null && curr.right != root) {
      curr = curr.right;
    }
  if (curr.right == root) {
    //if right child of inorder predecessor points to root node itself
    curr.right = null;
    root = root.right;
  } else {
    //otherwise
    System.out.print(root.data + " ");
    //traverse current node
    curr.right = root;
    //make right child of inorder predecessor point to this node
    root = root.left;
  }
}
}
}
public static void main(String args[]) {
  Node root = new Node(1);
  root.left = new Node(2);
  root.right = new Node(3);
  root.left.left = new Node(4);
  root.left.right = new Node(5);
  root.right.left = new Node(6);
  root.right.right = new Node(7);
  printPreorder(root);
}
}/*
-:Sample Input Tree:-
1
/ \
2 3
/ \ / \
4 5 6 7
-:Sample Output:-
1 2 4 5 3 6 7
-:Time Complexity:-
O(n) where n is the number of nodes in the given tree
-:Space Complexity:-
O(1)
*/