A binary search tree (BST) is a tree in which every node's left sub-tree has a key less than the node's key, and every right sub-tree has a key greater than the node's key. The major advantage of binary search trees is that the related sorting algorithms and search algorithms, such as in-order traversal, can be very efficient. This data structure is perfect for advanced interview questions.
The image to shows a sample Binary search tree with root 6 and leaves 1, 5 and 7.
During the interview you can expect a wide range of questions, such as searching a binary tree for a specific value, inserting and deleting nodes in the tree or sorting the tree. If you are asked to calculate the execution time of the algorithm you are implementing, always keep in mind the worst-case scenario, which is when the unbalanced tree resembles a linked list.
Problem 1. “Write a function which will search a given BST for a specific key and return a Value for the found node”
class Node{
public Node Right;
public Node Left;
public int Key;
public String Value;
}
Possible solution:
public static string FindBSTNode(Node root, int key)
{
if (root == null)
return null; // key is not found
string result;
if (key < root.Key)
result = FindBSTNode(root.Left, key);
else
if (key > root.Key)
result = FindBSTNode(root.Right, key);
else
result = root.Value; // key is found return value
return result;
}
This algorithm is quite simple. We begin by checking the key from the root node. If the root is null it either means the null node was passed to the function or we reached a leaf and have not found the key, which means the key is not in the tree at all. If the key is less than the root, then it must be in the left sub-tree, so we recursively call FindBSTNode for the left sub-tree key. Similarly, if the key is greater than the root, then it must be in the right sub-tree, so we recursively search the right part of the tree. If at some point the key we are searching for equals the root, it means we have found the node. Execution time for this algorithm is O(n) for the worst case scenario and comes to O(log2 n) for the well balanced tree.
Problem 2. “Write a function which will insert a number into the correct location of the Binary Search Tree”
Possible Solution:
private void AddNodeBST(int key, Node tree)
{
if (key == tree.Key) return;
// Smaller numbers go to the left
if (key < tree.Key)
{
if (tree.Left == null)
{
tree.Left= new BSTNode();
tree.Left.Key = key;
}
else
{ // use recursion to follow the tree
AddNodeBST(key, tree.Left);
}
}
// Larger and equal numbers go to the right
else
if (tree.Right == null)
{
tree.Right = new BSTNode();
tree.Right.Key = key;
}
else
{ // use recursion to follow the tree
AddNodeBST(key, tree.Right);
}
}
Problem 7. “Write a function which will flatten a binary tree into an array”
class Node{
public Node Right;
public Node Left;
public int Data;
}
Possible solution:
The solution, while being extremely simple, sometimes confuses many people because of the necessity of maintaining an array index for the next element. It can be solved with a simple recursion:
private static int FlattenTreeIntoArray(Node tree, int[] array, int i)
{
if (tree == null) return i; // We reached the end of the tree
// Flatten left subtree
i = FlattenTreeIntoArray(tree.Left, array, i);
// Get data from the current node
array[i] = tree.Data;
// Flatten right subtree
i = FlattenTreeIntoArray(tree.Right, array, i + 1);
return i;
}
Any takers to modify this code to flatten a binary tree into the link list?