Binary Trees - Interview Questions

Questions on binary trees are very frequently asked in interview questions.

Binary serach trees combine the advantages on ordered arrays and linked lists. Searches, insertions and deletions are fast with binary serach trees.

similar to other data structures, it is important to be thorough with the concepts of binary trees, the common operations performed on binary trees and the efficiency of these operations. Below interview questions on binary trees addresses some of these topics. Java programming language will be used for code snippets when applicable to depict these concepts of binary trees.

Trees are data structures that consist of nodes that are connected by edges.

Nodes can represent real world entities such as people, houses, cities etc. Edges represent the relationship between the nodes.

Typically there is a single node at the top row of the tree, more on the second row, and gradually increasing as we go down the rows of the tree.

**Tree Terminology**__Root__ - Root is the top node of a tree. A tree can have only one root. Every node must have only one path to the root of the tree.__Edge__ - Edge is the line connecting from one node to another__Path__ - Path is the connection from one node to another along the edges, and spanning multiple nodes.

Parent - Every node has an edge going upwards and connecting to another node called as its parent node.__Child__ - Every node can have one or more edges going downwards and connecting to nodes called child nodes.__Leaf__ - a node that does not have child nodes is called a leaf node.__Key__ - The data value represented by a node is called the key.

**Tree Representation**

Nodes in a tree are represented by circles containing the key value. Edges are represented as lines between the circles.

Binary trees are trees in which each node has at most two child nodes. The child node on the left is called the left child node and the child node on the right is called the right child node.

Binary search trees are binary trees in which a parent node's left child must have a key less than the parent node, and a parent node's right child must have a key greater than the parent node.

**Advantages of Binary Search Trees**

Binary search trees have the advantages of both ordered arrays and linked lists.

Searches are quick with ordered arrays, but insertions and deletions are slow. Insertions and deletions are quick with linked lists, but searches are slow.

Searches, insertions and deletions are fast with binary search trees.

In balanced trees there are approximately equal number of left descendant nodes and right descendant nodes. In unbalanced trees there are many more left descendant nodes than right descendant nodes, or vice versa.

Insertions, Deletions, Searches are the common operations performed on binary search trees.

The time efficiency of these operation on binary search trees is O(logN)

The node in a binary search tree has 4 key elements.

1. Key

2. Data

3. Reference to left child node

4. Reference to right child node

//Node

public class Node {

public int key;

public int data;

public Node leftChild;

public Node rightChild;

//constructor

public Node(int key, int data) {

this.key = key;

this.data = data;

this.firstChild = null;

this.rightChild = null;

}

}

Insertions, Deletions, Searches are the common operations performed on binary search trees.

The time efficiency of these operation on binary search trees is O(logN)

You can insert a new node in a binary tree by traversing the binary tree and finding the position to insert the node, i.e. finding the parent node for the new node to be inserted. You can then insert the new node by making it a child node of the parent node.

**Pseudocode**

1. Start with the root (current node). If root is null then root = new node.

2. If key of new node is less than key of root then go to left node, else go to right node. this becomes the current node

3. If key of new node is less than current node then go to left child, else go to right child.

4. Repeat step 3 until current node is null.

5. If current node is left of parent node insert the new node here by referring the left child of parent node to new node.

6. If current node is right of parent node, insert the node here by referring the right child of the parent node to the new node.

Following are key steps to perform searches on binary search trees.

1. Start at the root node and compare its value to the search key value.

2. If the search key value is less than the node value then go to the node's left child.

3. If the search key value is greater than the node value then go to the node's right child.

4. Repeat above steps for every child node that is visited.

Following are the key steps to perform insertions on binary search trees.

Perform search operation on the binary tree until the node to be deleted is found. The next steps depends on the number of child nodes that this node has. There are three possibilities

1. Node to be deleted has no children - If the node to be deleted has no children, i.e it is a leaf node, then just set the corresponding child reference (left child or right child) in the parent node to null.

2. Node to be deleted has one child - If the node to be deleted has only one child (say Node A), then set the corresponding child reference (left child or right child) in the parent node to this child node (Node A)

3. Node to be deleted has two children - If the node to be deleted has two children then replace the node with its in-order successor. The in-order successor is either the right child of the node to be deleted, or it can be a left descendant to right child of the node to be deleted.

A: In-order successor is the right child of the node to be deleted.

- Set the right child field (or left child field) of the parent node to the successor node.

- Set the left child field of the parent node to the left child field of the node to be deleted.

B: In-order successor is a left descendant to the right child of the node to be deleted

- successorParent.leftChild = successor.rightChild

- successor.rightChild = delNode.rightChild

parent.rightChild = successor

- successor.leftChild = current.leftChild

Subscribe to our Questions

MASTER Data Structures

Top ranked courses to help you master Data Structures skills.