Data structures are one of the most important and most asked concepts when it comes to the interviews of the computer science field. Data structures are basically a way to organize things using certain tools. Binary Search Tree is one of those data structures that organizes the data in a hierarchical fashion. Apart from other linear data structures like arrays or linked lists, this belongs to a nonlinear category of data structures and is a part of Tree data structures. In trees, the elementary component to hold the information is a node and these are diversified using different levels. Nodes on the lower levels and the ones that come out of an upper node are child nodes whereas the nodes on the upper levels are known as parent nodes. Here, let’s see some Binary Search Tree Interview Questions.
What is a Binary Search Tree?
A binary search tree is a specific type of tree under the tree data structures which has its own special criteria. If a tree needs to be a binary search tree then the basic conditions to be are:
- Each node must have at most two child nodes, which will be referred to as the left child node and the right child node. The topmost node from which these two child nodes will be outgrowing is known as Root Node.
- It has to meet the property of binary search that is, each node should be greater than or equal to the node present in the left subtree and less than the information stored in the node of the right subtree.
The usage of a binary search tree can be made clear by highlighting its property of being sorted. The keys are stored in a sorted sense which makes it easier to compare nodes which in turn helps in the variety of the problems which ranges from traversing the elements from root to child node to the easiness in the insertion, deletion, and comparison of the elements present. This easiness helps in forming complex codes way more easily and breaking them down into such modules. Also, the time taken in all of the above-mentioned tasks reduces to half as half of the tree is skipped while doing the comparisons.
Interview Questions on Binary Search Tree
A binary search tree is one of the most popular concepts when data structures are asked in an interview. Its versatility and the sorted nodes system accompany many complex and basic questions to ask and test the knowledge of the applicant. Apart from the heavy codes, there are certain questions that are being asked in many interviews and are very common in this field. Obviously, the questions that require complex thinking will also be covered but the codes for the same can be constructed by the idea provided in the sample answers. Therefore, below are the set of questions asked in interviews when binary search tree is the concept to focus on. They are:
- What are root node and leaf node in binary search tree?
The root node in a binary search tree is referred to as the topmost node present in the binary search tree whereas the leaf node is referred to as any end node of the tree, that is, the node that doesn’t have any child node is known as a leaf node.
- How to find the distance between two nodes in a binary tree?
While finding the distance between any two nodes of a binary search tree, one must always look for the number of edges involved in between. Assume two nodes A and B of a binary search tree then the distance between these two nodes is the minimum number of edges to traverse to reach point B from point A or vice-versa.
- Define Self-Balanced Tree.
A tree is a self-balanced tree if that particular tree is able to keep its height as small as possible when certain operations like deletion or insertion are executed. For a binary search tree to be a self-balanced tree it has to meet both the conditions, that is that of the binary search tree and self-balanced tree. Thus a binary search tree is a self-balanced tree if the left subtree contains smaller values and the right subtree has all the greater value elements. To ensure this the processes used are:
- Left Rotation
- Right Rotation
- How to convert a binary tree into a binary search tree?
A binary tree to be a binary search tree has to convert in such a way that the left subtree contains all the elements of lower values whereas the elements on the right subtree should be of higher values. For that, we can complete the transition by:
- A temporary array is created that stores the in-order traversal of the binary tree.
- Using any sorting algorithm, sort the elements of the temporary array that contains in order traversal of the tree.
- Again initiate an in-order traversal on the tree and then copy the elements by assigning each node the value one by one.
By this in the end all the lower values will be adjusted to the left and higher ones on the right. Thus, a binary tree is converted into a binary search tree.
- How to delete a node from a binary search tree?
Deletion of a node done on BST is considered typical as after the operation is done, the properties of the binary search tree should be reinstated.
This can be done as follows:
To consider the node to be deleted, it can either be a leaf node or contains one child or has two children. To answer the question one can:
- For the leaf node to delete, reach the node and delete it.
- For the node to be deleted having one child, the element present on the child node shall be copied to the node to be deleted and delete the child node.
- For the node carrying two children, finding the in-order successor is a must. After the in-order successor is found, copy the element information to the node to be deleted and then delete them in-order successor which will, in turn, remove the desired node.
- How to find if the two trees given are identical or not?
For two trees to be identical the data present in them and the arrangement of both the trees should be the same. To find if they are identical or not, we have to traverse both the tress and compare the arrangement. To do so, follow the steps given below:
- Check the data present in the root node of both the tree.
- Using recursive functions check the left subtree of the tree by calling it again and again for both the trees.
- Same as above but for the right subtree
- When done, if all the three steps above mentioned gives the same result then the two trees given to compare are identical and if any one of the results differs then the trees are not identical.
- What is an AVL tree?
An AVL tree is a part of the tree family that is self-balancing and checks the height of its left subtree and height of the right subtree and also ensures that their difference is not more than 1. This difference is known as the Balance Factor. The tree got its name from its inventors Adelson, Velski, and Landis. The initials from their name served as the name for this special kind of tree. It is self-balancing and always maintains the balance factor as 1. If the factor is more than 1 then the tree follows a balancing operation using the following steps. They are:
- Left Rotation
- Right Rotation
- Left-Right Rotation
- Right-Left Rotation
- How to find in order the predecessor of a node in a binary search tree?
In order predecessor of a node in a binary search tree is the element present just before the asked node in the in-order traversal of the binary search tree. The in-order predecessor of a node is the node with the highest value present in the left subtree or the right-most child of the left subtree. If the left subtree is absent then the ancestor node is the in order predecessor of that node. Moving up in the tree where a node is the right child of a tree will serve the purpose. If this condition is also not met then there is no in order predecessor of that particular node.
- How to find the Lowest Common Ancestor of two nodes in a binary search tree?
The Lowest Common Ancestor of any two nodes says A and B, is the deepest node that involves both A and B as its descendants with each node being a descendant of itself. Simply put, it is the deepest or the farthest located shared ancestor of both A and B from the root. The easiest way to find the Lowest Common Ancestor of two nodes, say A and B, is to firstly store the path from root to A node and storing it in an array. Again, traversing the path from the root to node B and storing it in a different array. Once done, compare both the arrays and the last matched value will be the Lowest Common Ancestor of the nodes A and B. There are other approaches also using iterative function and recursive functions but this approach is the easiest and simple to carry out.
- How to merge two binary search trees into a doubly-linked list in sorted order?
The basic way is to convert both the trees into individual linked lists and then merge both the linked list into a singly linked list in sorted order. By this, the desired output will be achieved. In order to complete the first step of the process, to convert a tree into a linked list, reversed in order traversal of the tree should be performed in which the right child node is accessed before the left one. Each node accessed in the reverse in order traversal will be inserted in the front of the doubly linked list and thus one by one the two linked lists will be merged into a doubly linked list in a sorted manner.
By this, all the basic questions asked in interviews regarding Binary Search Tree are mentioned above with the sampling approach to hit it with before constructing the codes. This will give the idea of how to initiate and will break down questions to give clarity to answer the question efficiently. Hope you will find it helpful in your forthcoming interviews. Best of Luck!
