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 subtree, and less than or equal to any key stored in the right subtree.

Binary search trees allow 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, based on 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 listed out commonly asked interview questions on Binary Search Tree:

  1. Insertion in a BSTEasy
  2. Search a given key in BSTEasy
  3. Deletion from BST (Binary Search Tree)Medium
  4. Construct a balanced BST from the given keysEasy
  5. Determine whether a given binary tree is a BST or notMedium
  6. Check if the given keys represent the same BSTs or not without building BSTHard
  7. Find inorder predecessor for the given key in a BSTMedium
  8. Find the Lowest Common Ancestor (LCA) of two nodes in a BSTEasy
  9. Find k’th smallest and k’th largest element in a BSTEasy
  10. Find floor and ceil in a Binary Search TreeMedium
  11. Convert a binary tree to BST by maintaining its original structureMedium
  12. Remove nodes from a BST that have keys outside a valid rangeMedium
  13. Find a pair with the given sum in a BSTEasy
  14. Find k’th smallest node in a Binary Search Tree (BST)Easy
  15. Find inorder successor for the given key in a BSTMedium
  16. Replace every array element with the least greater element on its rightMedium
  17. Fix a binary tree that is only one swap away from becoming a BSTHard
  18. Update every key in a BST to contain the sum of all greater keysMedium
  19. Check if a given sequence represents the preorder traversal of a BSTHard
  20. Build a Binary Search Tree from a postorder sequenceHard
  21. Build a Binary Search Tree from a preorder sequenceHard
  22. Count subtrees in a BST whose nodes lie within a given rangeMedium
  23. Find the size of the largest BST in a binary treeHard
  24. Print complete Binary Search Tree (BST) in increasing orderEasy
  25. Print binary tree structure with its contents in C++Medium
  26. Find optimal cost to construct a binary search treeHard
  27. Treap Data StructureBeginner
  28. Implementation of Treap Data Structure (Insert, Search, and Delete)Hard
  29. Merge two BSTs into a doubly-linked list in sorted orderHard
  30. Construct a height-balanced BST from an unbalanced BSTHard
  31. Construct a height-balanced BST from a sorted doubly linked listHard
  32. Find a triplet with the given sum in a BSTHard
  33. Convert a Binary Search Tree into a Min HeapHard

 
Also See:

Binary Tree – Interview Questions and Practice Problems

Rate this post

Average rating 4.84/5. Vote count: 98

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?

Thanks for reading.

To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and support our growth. Happy coding :)


guest
1 Comment
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Do NOT follow this link or you will be banned from the site!