Binary Search Tree (BST) Interview Questions and Practice Problems

 
A Binary Search Tree (BST) is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child and the topmost node in the tree is called the root. It additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Binary search trees allows fast lookup, addition and removal of items. They keep their keys in sorted order, so that lookup and other operations can use the principle of Binary Search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

 
In this post, we have list out commonly asked interview questions on Binary Search Tree –

 

  1. Insertion in BST
     
  2. Search given key in BST
     
  3. Deletion from BST
     
  4. Construct balanced BST from given keys
     
  5. Determine if given Binary Tree is a BST or not
     
  6. Check if given keys represents same BSTs or not without building the BST
     
  7. Find inorder predecessor for given key in a BST
     
  8. Find Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree
     
  9. Find Kโ€™th smallest and Kโ€™th largest element in BST
     
  10. Floor and Ceil in a Binary Search Tree
     
  11. Find optimal cost to construct binary search tree
     
  12. Convert a Binary Tree to BST by maintaining its original structure
     
  13. Remove nodes from BST that have keys outside the valid range
     
  14. Find a pair with given sum in a BST
     
  15. Find inorder successor for given key in a BST
     
  16. Replace every element of an array with the least greater element on its right
     
  17. Fix a binary tree that is only one swap away from becoming a BST
     
  18. Update every key in BST to contain sum of all greater keys
     

 
 

Thank you for being with us. ๐Ÿ™‚

 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
ram
Guest

Great Blog !
But in the current post, description is of Binary Search and Questions are of Binary Search Tree(BST)