Binary Search Tree

Learn more about Binary Search Tree in DSA Self Paced Course
Practice Problems on Binary Search Tree !

What is Binary Search Tree?

Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Binary Search Tree

Introduction:

1. Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials
2. Applications of BST
3. Application, Advantages and Disadvantages of Binary Search Tree

Basic Operations:

1. Insertion in Binary Search Tree
2. Searching in Binary Search Tree
3. Deletion in Binary Search Tree
4. Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order
5. Convert a normal BST to Balanced BST

Standard problems on BST

• Easy:
  1. Iterative searching in Binary Search Tree
  2. A program to check if a binary tree is BST or not
  3. Binary Tree to Binary Search Tree Conversion
  4. Find the node with minimum value in a Binary Search Tree
  5. Check if an array represents Inorder of Binary Search tree or not
  6. How to determine if a binary tree is height-balanced?
  7. Sorted Array to Balanced BST
  8. Check for Identical BSTs without building the trees
  9. Convert BST to Min Heap
  10. Second largest element in BST
  11. Add all greater values to every node in a given BST
  12. Check if two BSTs contain same set of elements
  13. Sum of k smallest elements in BST
• Medium:
  1. Construct BST from given preorder traversal | Set 1
  2. Sorted Linked List to Balanced BST
  3. Transform a BST to greater sum tree
  4. BST to a Tree with sum of all smaller keys
  5. Construct BST from its given level order traversal
  6. Check if the given array can represent Level Order Traversal of Binary Search Tree
  7. Lowest Common Ancestor in a Binary Search Tree
  8. Find k-th smallest element in BST (Order Statistics in BST)
  9. K’th Largest element in BST using constant extra space
  10. Largest number in BST which is less than or equal to N
  11. Find distance between two nodes of a Binary Search Tree
  12. Largest BST in a Binary Tree | Set 2
  13. Remove all leaf nodes from the binary search tree
  14. Inorder Successor in Binary Search Tree
  15. Find a pair with given sum in BST
  16. Maximum element between two nodes of BST
  17. Find the largest BST subtree in a given Binary Tree
  18. Find a pair with given sum in a Balanced BST
  19. Two nodes of a BST are swapped, correct the BST
  20. How to handle duplicates in Binary Search Tree?
  21. Leaf nodes from Preorder of a Binary Search Tree (Using Recursion)
• Hard:
  1. Construct all possible BSTs for keys 1 to N
  2. In-place Convert BST into a Min-Heap
  3. Check given array of size n can represent BST of n levels or not
  4. Merge two BSTs with limited extra space
  5. K’th Largest Element in BST when modification to BST is not allowed
  6. Check if given sorted sub-sequence exists in binary search tree
  7. Maximum Unique Element in every subarray of size K
  8. Count pairs from two BSTs whose sum is equal to a given value x
  9. Print BST keys in given Range | O(1) Space
  10. Inorder predecessor and successor for a given key in BST
  11. Find if there is a triplet in a Balanced BST that adds to zero
  12. Replace every element with the least greater element on its right
  13. Count inversions in an array | Set 2 (Using Self-Balancing BST)
  14. Leaf nodes from Preorder of a Binary Search Tree
  15. Minimum Possible value of |ai + aj – k| for given array and k.
  16. Special two digit numbers in a Binary Search Tree
  17. Merge Two Balanced Binary Search Trees

Some Quizzes:

• ‘Quizzes’ on Binary Search Tree
• ‘Quizzes’ on Balanced Binary Search Trees

Quick Links :

• ‘Practice Problems’ on Binary Search Tree
• Videos on Binary Search Tree

Recomended:

• Learn Data Structure and Algorithms | DSA Tutorial