Tech interviews for software engineers and developers focus a lot on fundamentals such as data structures and algorithms. While preparing for coding interviews, engineers must brush up on all the basics, such as stacks, queues, and trees. In this article, we’ll be focusing on the binary search tree:

We’ll cover:

• What is a binary search tree
• Functionalities of a binary search tree
• Binary search tree algorithms and their implementation (search, insertion, deletion)
• Strengths and weaknesses of the binary search tree
• Examples of tech interview problems and questions on binary search tree
• FAQs on binary search tree

What Is a Binary Search Tree?

A binary search tree (or BST) is a rooted binary tree, where each node stores a key. The two children of any binary search tree node are generally referred to as the left and the right child. The nodes in the tree are arranged in such a way that follows these properties:

• The key at any node must be greater than all of the keys from the node’s left subtree. 
• The key at any node must be smaller than all of the keys from the node’s right subtree. 

Notice that the rooted binary tree above follows the properties of a binary search tree. But, on the other hand, the tree below is a rooted binary tree but not a binary search tree. Can you tell the reason?

In the above binary tree, the number 13 is placed in the root’s left subtree, which contains the key 7. But in a binary search tree, 13 would be placed in the right subtree of the root. 

Binary search tree has many real-world applications, including 3D game engines, data compression codes, and Unix kernel codes. 

Functionalities of a Binary Search Tree

Consider the problem of finding an element/number in a collection/array of size n. If the numbers are not sorted, we must iterate through the whole container to check the sought element’s existence. If the array was sorted, we could apply binary search and find the element or conclude that the element doesn’t exist in logarithmic time complexity. 

Now, assume that some numbers will be added to or removed from the collection, and we would have to search for an element again. We cannot add/remove a number from an array in less than O(n) operations. But with the help of a “non-linear” data structure like a balanced binary search tree, we can perform search, insertion, addition, deletion, etc., in O(log n) time complexity. 

Note that, in this article, we would develop a binary search tree that might not be balanced. A balanced binary search tree is a binary search tree with O(log n) height, where n is the number of nodes in the binary search tree. Understanding the working principles of such a binary tree is important for understanding how a height-balanced binary search tree works. 

Binary Search Tree Algorithms

As described earlier, the binary search tree is a very useful data structure and allows different types of operations such as insertion, deletion, search, etc. Here, we will look into the details of how these operations are performed.

Algorithm for Search Operation in a Binary Search Tree

A search operation in a Binary Search Tree algorithm aims to locate a particular key within the tree. Though it might seem a little complicated, the fact that nodes in a binary search tree follow an orderly arrangement makes it quite easy to locate a particular key in the tree.

For any node, all the nodes in its left subtree will have a key smaller than the key at that node. Also, all the nodes in its right subtree will have a key greater than the key at that node. 

Here's how the Binary Search Tree Search algorithm goes for a given query key:

1. We start our search operation at the root of the binary tree. We compare the key at the root node with the query key. If they are equal, we report that the sought key has been found.  Otherwise, there can be two cases: 

         a. Query key is smaller than the key at the root node: It becomes apparent that the right subtree does not have the key. In such a case, only a search in the left         subtree is needed. 

         b. Query key is greater than the key at the root node: It becomes evident that the node is not present in the left child; we can safely limit our search operation to the         right subtree. 

2. Upon limiting our search space to one of the subtrees, we recursively apply the same searching technique in the limited subtree. Note that every subtree in a binary search tree is also a smaller binary search tree itself. So, we can reciprocate the same technique to search for the query key in the selected subtree. 

We continue our search until finding a node with the sought key or ending up in a null node. If we end up in a null node, we can conclude that the query key is not present in the binary search tree.
Let us go through an example: 

Let’s look for the number 15 in the binary search tree below

We start our search process at the root. But since 15 > 7, we limit our search operation to its right subtree.

Now we are executing the search operation at the binary search tree rooted at the node with key = 12. Since 15 > 12, we will again move towards its right subtree. 

Now we are executing the search operation at the binary search tree rooted at the node with key = 25. Since 15 < 25, we are supposed to move towards its left subtree. But as it is a null node, we can conclude that the key 15 does not exist in the BST. 

It is easy to notice that the algorithm will execute O(height) operations to find a number. 

Algorithm for Insert Operation in a Binary Search Tree

While inserting a key, we must not violate the properties of a binary search tree. Moreover, we are assuming that the binary search tree will not contain any duplicate numbers. In other words, there wouldn’t be any insertion request for a key that already exists in the binary search tree. Look at the FAQ section to know how to deal with duplicate numbers in a binary search tree. 

Here's how the Binary Search Tree Insertion algorithm goes for a given key:

1. We start our insert operation at the root of the binary tree. We compare the key at the root node with the key to be inserted. There can be two cases: 

          a. The key to be inserted is smaller than the key at the root node: It becomes apparent that the key can not be inserted to the right subtree of the root node. In         such a case, we move toward the left subtree. 

          b. The key to be inserted is greater than the key at the root node: To maintain the properties of a binary search tree, we must insert the key at the right subtree. 

2. Upon deciding in which subtree the new key should go, we recursively apply the same insertion technique in the limited subtree. 

We repeat the above two steps until reaching a null node. Once we reach a null node, we replace that null node with a node with the given key to be inserted. Let’s look at an example.

Let’s try to insert the number 11 to the following BST. 

We start at the root node. As 11 > 7, we need to move towards its right subtree. 

As 11 < 12, we move towards the left subtree of the node containing the key = 12.

As 11 > 8, we move towards the right subtree. 

As 11 > 10, we move towards the right subtree and encounter a null node. This is where we insert the key 11 as a node to get the following binary search tree. 

It is easy to notice that the algorithm will execute O(height) operations to insert a number. 

Algorithm for Deletion in a Binary Search Tree

In this section, we will look at how to delete a key from a binary search tree. To delete the key, we will delete the node containing that key. The algorithm for deletion is a little complicated to the other algorithms. There can be three cases in total. Let us look at each case separately. 

Case #1: Deleting a Node With No Child

This is the simplest of the three cases. We need to follow the steps below:

1. Locate the node to be deleted. 
2. Replace it with a null node and free the memory created for the node to be deleted.

Let’s go through an example. 

Let’s delete the key 4 from the following binary search tree. 

We need to first locate the key 4 and then delete it from the best. 

As 4 < 7, so we move to the left subtree of the root node.

As 2 > 4, we move to its right subtree. 

Upon finding the node, as it doesn’t have any children, we simply remove it from the binary search tree. 

Case #2: Deleting a Node With Only One Child 

We need to follow the steps below to delete a node with a single child:

1. Locate the node in the binary search tree. There can be two cases:

a. If the node is located at the root, Take the only child of it and make it the new root of the binary search tree. After that, remove the link between the new root node and the node to be deleted.  

b. Otherwise, link the parent of the node to be deleted with the only child of the node to be deleted. This can also be thought of as replacing the node to be deleted with its only child. 

2. At this step, the node to be deleted should have been removed from the binary search tree. After that, safely free the memory used for storing the information about the node to be deleted. 

Let’s look at an example:

Let us try deleting the number 8 from the binary search tree below.

As 8 > 12, we need to move towards the right subtree. 

As 8 < 12, we move toward the left subtree. 

Upon reaching the key 8, we replace it with its only child and get the following binary search tree. 

Case #3: Deleting a node with two children. 

We need to follow the steps below: 

1. Locate the node to be deleted. 
2. Replace its key with the key’s predecessor or successor in the subtree of the located node. The predecessor of a particular key is the largest key which is smaller than that particular key. Similarly, the successor of a particular key is the smallest key which is larger than that particular key.
   
   In order to find the predecessor of a key, we need to move to the left subtree once and then keep moving right as long as possible. Similarly, we can find the successor by going to the right subtree once and then going left as long as possible.
   
   After finding the node’s predecessor/successor, we can delete this predecessor/successor node and replace the key of the node to be deleted with the key of the predecessor/successor. It is easy to notice that the predecessor/successor will have at most one child. So, we can delete it in the methods discussed in Case #2. 

Let’s go through an example:

Let’s try to delete the number 12 from the binary search tree below.

As 12 > 7, we need to move towards the right subtree. 

We found the node to be deleted. But we now need to find 12’s predecessor/successor to replace it with 12. Let’s replace 12 with its predecessor. To find the predecessor, we need to move to the left subtree once and then keep moving to the right subtree as long as possible because it will take us to the largest number smaller than 12 in its subtree. 

After moving once, we keep going right as long as possible.

We can not go any further in the right subtree once we end up with the number 10. So we delete this key in order to replace it with the key 12. 

After deleting 12’s predecessor, we replace 12 with its predecessor to get the following binary search tree. 

It is easy to notice that the algorithm will execute O(height) operations to delete a number. 

Implementation of Search, Insertion, and Deletion in a Binary Search Tree

Following is an implementation of the algorithms described above in C++: 

#include<iostream>

using namespace std;

struct node{

    int key;

    node *left_ptr, *right_ptr;

};

// Prints the keys in sorted order

void inorder_traversal(node *root){

    if(root == NULL){

        return;

    }

    inorder_traversal(root->left_ptr);

    printf("%d ", root->key);

    inorder_traversal(root->right_ptr);

}

/*

    Parameters:

        - key: the element to be inserted

        - root: the root of the binary search tree where the element has to be inserted

    Return value:

        - the root of the binary search tree after performing the insertion operation

*/

node* insert(node *root, int key){

    if(root == NULL){

        root = new node({key});

        return root;

    }

    if(root->key < key) {

        root->right_ptr = insert(root->right_ptr, key);

        return root;

    }

    else{

        root->left_ptr = insert(root->left_ptr, key);

        return root;

    }

}

/*

    Parameters:

        - key: the element to be searched

        - root: the root of the binary search tree where the element has to be searched

    Return value:

        - true, if the element is found in the binary search tree

        - false, otherwise

*/

bool search(node *root, int key){

    if(root == NULL){

        return false;

    }

    if(root->key == key){

        return true;

    }

    if(root->key < key){

        return search(root->right_ptr, key);

    }

    else{

        return search(root->left_ptr, key);

    }

}

/*

    Parameters:

        - key: the element to be deleted

        - root: the root of the binary search tree from which the element has to be deleted

    Return value:

        - the root of the binary search tree after performing the deletion operation

*/

node * remove(node *root, int key){

    if(root == NULL){

        return NULL;

    }

    if(root->key == key){

        // Case 1: the node to be deleted has no child

        if(root->left_ptr == NULL && root->right_ptr == NULL){

            delete(root);

            return NULL;

        }

        // Case 2: the node to be deleted has at most one child

        if(root->left_ptr == NULL){

            // Storing the address of the node to be returned before deleting the root node.

            node *ret = root->right_ptr;

            delete(root);

            return ret;

        }

        if(root->right_ptr == NULL){

            // Storing the address of the node to be returned before deleting the root node.

            node *ret = root->left_ptr;

            delete(root);

            return ret;

        }

        // Case 3: the node to be deleted has both children

        node *predecessor = root->left_ptr;

        while(predecessor->right_ptr != NULL){

            predecessor = predecessor->right_ptr;

        }

        int replacement_value = predecessor -> key;

        // The predecessor node will have at most one child and it can be deleted using the method stated above.

        root = remove(root, predecessor->key);

        // Replacing the key of the node to be deleted with the its predecessor.

        root->key = replacement_value;

        return root;

    }

    if(root->key < key){

        root->right_ptr = remove(root->right_ptr, key);

        return root;

    }

    else{

        root->left_ptr = remove(root->left_ptr, key);

        return root;

    }

}

int main()

{

    node *bst = NULL;

    bst = insert(bst, 7);

    bst = insert(bst, 2);

    bst = insert(bst, 4);

    bst = insert(bst, 12);

    bst = insert(bst, 8);

    bst = insert(bst, 10);

    bst = insert(bst, 25);

    printf("Currently existing number in the binary search tree: ");

    inorder_traversal(bst);

    puts("\n");

    puts("Searching for the number 15 in the binary search tree.");

    if(search(bst, 15) == true){

        puts("The number 15 is present in the binary search tree.\n");

    }

    else{

        puts("The number 15 is not present in the binary search tree.\n");

    }

    puts("Removing the number 4 from the binary search tree.");

    bst = remove(bst, 4);

    printf("Currently existing number in the binary search tree: ");

    inorder_traversal(bst);

    puts("\n");

    puts("Inserting number 4 again.");

    bst = insert(bst, 4);

    printf("Currently existing number in the binary search tree: ");

    inorder_traversal(bst);

    puts("\n");

    puts("Removing the number 12 from the binary search tree.");

    bst = remove(bst, 12);

    printf("Currently existing number in the binary search tree: ");

    inorder_traversal(bst);

    puts("\n");

    return 0;

}

Output of the code:

Currently existing number in the binary search tree: 2 4 7 8 10 12 25

Searching for the number 15 in the binary search tree.

The number 15 is not present in the binary search tree.

Removing the number 4 from the binary search tree.

Currently existing number in the binary search tree: 2 7 8 10 12 25

Inserting number 4 again.

Currently existing number in the binary search tree: 2 4 7 8 10 12 25

Removing the number 12 from the binary search tree.

Currently existing number in the binary search tree: 2 4 7 8 10 25

Strengths and Weaknesses of the Binary Search Tree

Strength:

Height-balanced binary search tree enables us to search/insert/delete a number from a collection in logarithmic time complexity. In an array or linked list, each such operation would take linear time on average. 

Weakness:

A binary search tree may not yield an impressive performance if it is unbalanced. While some binary search trees are height-balanced, others are not. Some other data structures, such as arrays, have been shown to execute algorithms faster than binary search trees if they are not height-balanced. 

Examples of Tech Interview Problems and Questions on Binary Search Tree

Here are a few problems and questions on binary search tree that a software developer or coding engineer can expect at technical interviews at FAANG and other tech companies:

1. Create a binary search tree from a given preorder traversal by applying recursion.
2. Find out if a given binary tree is a binary search tree.
3. Apply binary search tree algorithms to determine the lowest common ancestor of two given nodes in a binary search tree.
4. Convert a sorted singly linked list array into a binary search tree.
5. Construct a binary search tree with the minimum height from a sorted array with unique elements.
6. A binary search tree has X nodes, and two nodes, P and Q. Use this information to find the median of all the nodes in the given binary search tree lying in the range [P, Q].
7. Construct a binary tree that is only one swap away from becoming a binary search tree.
8. Print a complete binary search tree in increasing order.
9. Create a height-balanced binary search tree from an unbalanced binary search tree.
10. You have the root node of a binary search tree and an integer n. Use this data to return the nth (1-indexed) least node/element in the tree.
11. Combine two binary search trees into a double-linked list in a sorted manner.
12. Create a height-balanced binary search tree from an unsorted integer array that represents binary search tree keys.
13. Whiteboard the code (Java) to delete nodes from a binary search tree with keys beyond a given range.
14. Reconstruct a given binary search tree such that every key in it is modified to contain the sum of all greater keys present in the binary search tree.
15. You are given a Binary Tree. Can you find the size of the largest binary search tree present in it?
    

16. How do you find the distance between two random nodes in a given binary search tree?
17. How would you find the sum of the deepest leaves in a binary tree?
18. Can you write a function to determine if two given binary search trees are mirror images of each other?

FAQs on Binary Search Tree 

Question 1. What do these terms mean with respect to a binary search tree: leaf node, root node, and self-balanced tree?

Answer: If a node in a binary tree is without any children, we refer to it as a leaf node. The first node or the topmost node in a tree is referred to as the root node. A self-balanced binary search tree is one that can minimize its height as far as possible when nodes are inserted or deleted from the binary search tree.

Question 2: How to handle duplicates in a binary search tree?

‍Answer: A good idea will be to add another attribute to the “node” class that will track the frequency of the key present at that node. Upon receiving an insertion request for a key that already exists in the binary search tree,  we can just increase the node’s frequency. On the other hand, if the sought key is not present in the array, we can create a new node with that key and set its frequency equal to 1. The other operations like deletion and search can be done similarly.

Ace Your Next Tech Interview With Interview Kickstart!

If you’re looking for guidance and help to nail your next technical interview, sign up for our free webinar. 

As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land their dream jobs at Google, Facebook, Apple, Netflix, Amazon, and other Tier-1 tech companies.

Join our webinar to learn more!