Most Asked Binary Search Tree (BST) Coding Problems in Interviews

Table of Contents#

1. Check if a Binary Tree is a Binary Search Tree#

Problem Statement#

Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST is defined as:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be valid BSTs.

Approach#

A common mistake is to check only the immediate left and right children. Instead, we need to ensure all nodes in the left subtree are less than the current node, and all nodes in the right subtree are greater. This can be done using a recursive approach with bounds:

• Track the allowed range (min_val, max_val) for the current node.
• For the root, the range is (-infinity, +infinity).
• For the left child, update the upper bound to the current node’s value.
• For the right child, update the lower bound to the current node’s value.

Solution Code#

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def is_valid_bst(root: TreeNode) -> bool:
    def helper(node, min_val, max_val):
        if not node:
            return True  # Empty tree is valid
        # If current node's value violates the min/max constraint
        if not (min_val < node.val < max_val):
            return False
        # Recursively check left and right subtrees with updated bounds
        return (helper(node.left, min_val, node.val) and 
                helper(node.right, node.val, max_val))
    
    return helper(root, float('-inf'), float('inf'))

Explanation#

• Base Case: An empty tree (None) is always a valid BST.
• Bounds Check: For each node, ensure its value lies between min_val (lower bound) and max_val (upper bound).
• Recursion: For the left child, the upper bound becomes the current node’s value. For the right child, the lower bound becomes the current node’s value.

Time & Space Complexity#

• Time Complexity: O(n), where n is the number of nodes. Each node is visited exactly once.
• Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. For a balanced BST, h = log n; for a skewed BST, h = n.

2. Insert a Node in a BST#

Problem Statement#

Given the root of a BST and a value, insert the value into the BST at the correct position. Return the root of the modified BST.

Approach#

Insertion in a BST follows the property:

• If the value is less than the current node, insert it into the left subtree.
• If the value is greater than the current node, insert it into the right subtree.
• If the subtree is empty (current node is None), create a new node with the value and return it.

Solution Code#

def insert_into_bst(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)  # Insert new node here
    if val < root.val:
        root.left = insert_into_bst(root.left, val)  # Insert in left subtree
    else:
        root.right = insert_into_bst(root.right, val)  # Insert in right subtree
    return root

Explanation#

• Base Case: If root is None, the value belongs here—return a new TreeNode with val.
• Recursion: Traverse left or right based on the comparison between val and root.val, and update the left/right child with the result of the recursive call.

Time & Space Complexity#

• Time Complexity: O(h), where h is the height of the BST.
• Space Complexity: O(h) for the recursion stack (O(1) for an iterative approach).

3. Delete a Node in a BST#

Problem Statement#

Given the root of a BST and a key, delete the node with the given key. Return the root of the modified BST.

Approach#

Deletion in a BST has three cases:

1. Node is a Leaf: Simply remove the node (set parent’s child to None).
2. Node has One Child: Replace the node with its child.
3. Node has Two Children: Replace the node with its inorder successor (smallest node in the right subtree) or inorder predecessor (largest node in the left subtree), then delete the successor/predecessor.

Solution Code#

def delete_node(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None  # Key not found
    
    # Step 1: Find the node to delete
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # Step 2: Node found; handle deletion cases
        # Case 1: No left child (replace with right)
        if not root.left:
            return root.right
        # Case 2: No right child (replace with left)
        elif not root.right:
            return root.left
        # Case 3: Two children; find inorder successor (min of right subtree)
        else:
            # Find min in right subtree
            successor = root.right
            while successor.left:
                successor = successor.left
            # Replace current node's value with successor's value
            root.val = successor.val
            # Delete the successor from the right subtree
            root.right = delete_node(root.right, successor.val)
    
    return root

Explanation#

• Finding the Node: Traverse the tree to locate the node with key.
• Case Handling:
  • Leaf Node: Return None to remove the node.
  • One Child: Return the existing child to replace the node.
  • Two Children: Replace the node’s value with the inorder successor (smallest in the right subtree), then delete the successor (which will be a leaf or have one child).

Time & Space Complexity#

• Time Complexity: O(h), where h is the height of the BST.
• Space Complexity: O(h) for the recursion stack.

4. Find Minimum/Maximum Element in a BST#

Problem Statement#

Find the minimum and maximum values in a BST.

Approach#

• Minimum Element: The leftmost node in the BST (traverse left until left is None).
• Maximum Element: The rightmost node in the BST (traverse right until right is None).

Solution Code#

def find_min(root: TreeNode) -> int:
    current = root
    while current.left:
        current = current.left
    return current.val
 
def find_max(root: TreeNode) -> int:
    current = root
    while current.right:
        current = current.right
    return current.val

Explanation#

• Minimum: Start at root and move left until no more left children exist. The last node is the minimum.
• Maximum: Start at root and move right until no more right children exist. The last node is the maximum.

Time & Space Complexity#

• Time Complexity: O(h), where h is the height of the BST.
• Space Complexity: O(1) (iterative approach, no extra space).

5. Find the Inorder Successor/Predecessor of a Node in BST#

Problem Statement#

Given a BST and a node, find its inorder successor (smallest node greater than the given node) and predecessor (largest node smaller than the given node).

Approach#

• Inorder Successor:
  • If the node has a right subtree, the successor is the minimum node in the right subtree.
  • Else, traverse up the tree to find the first ancestor where the node lies in the left subtree.
• Inorder Predecessor:
  • If the node has a left subtree, the predecessor is the maximum node in the left subtree.
  • Else, traverse up to find the first ancestor where the node lies in the right subtree.

Solution Code (Successor)#

def inorder_successor(root: TreeNode, node: TreeNode) -> TreeNode:
    successor = None
    current = root
    while current:
        if current.val > node.val:
            successor = current  # Potential successor
            current = current.left  # Look for smaller successor
        elif current.val < node.val:
            current = current.right
        else:
            # Node found; check right subtree for min
            if current.right:
                temp = current.right
                while temp.left:
                    temp = temp.left
                successor = temp
            break
    return successor

Explanation#

• Right Subtree Check: If the node has a right subtree, the successor is the leftmost node in the right subtree.
• Ancestor Traversal: If no right subtree, track the last ancestor where the node was in the left subtree (this ancestor is the successor).

Time & Space Complexity#

• Time Complexity: O(h), where h is the height of the BST.
• Space Complexity: O(1) (iterative approach).

6. Lowest Common Ancestor (LCA) in a BST#

Problem Statement#

Given a BST and two nodes p and q, find their lowest common ancestor (the deepest node that has both p and q as descendants).

Approach#

Leverage the BST property:

• If both p and q are smaller than the current node, LCA is in the left subtree.
• If both are larger, LCA is in the right subtree.
• Else, the current node is the LCA (since p and q are in different subtrees).

Solution Code#

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current  # LCA found
    return None

Explanation#

• Traversal: Start at root and compare p.val and q.val with current.val.
• Decision: Move left/right if both nodes are in that subtree; otherwise, current is the LCA.

Time & Space Complexity#

• Time Complexity: O(h), where h is the height of the BST.
• Space Complexity: O(1) (iterative approach).

7. Kth Smallest Element in a BST#

Problem Statement#

Given a BST, find the kth smallest element (1-based index).

Approach#

Inorder traversal of a BST yields elements in sorted order. Use iterative inorder traversal to stop early once the kth element is found.

Solution Code#

def kth_smallest(root: TreeNode, k: int) -> int:
    stack = []
    current = root
    while stack or current:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()  # Visit node
        k -= 1
        if k == 0:
            return current.val
        current = current.right  # Move to right subtree

Explanation#

• Iterative Inorder: Use a stack to simulate recursion. Traverse left, pop nodes, and decrement k until k == 0 (kth smallest found).

Time & Space Complexity#

• Time Complexity: O(h + k), where h is the height and k is the input. In the worst case (k = n), O(n).
• Space Complexity: O(h) for the stack.

8. Kth Largest Element in a BST#

Problem Statement#

Given a BST, find the kth largest element (1-based index).

Approach#

Reverse inorder traversal (right → root → left) yields elements in descending order. Stop when the kth element is found.

Solution Code#

def kth_largest(root: TreeNode, k: int) -> int:
    stack = []
    current = root
    while stack or current:
        # Traverse to the rightmost node
        while current:
            stack.append(current)
            current = current.right
        current = stack.pop()  # Visit node
        k -= 1
        if k == 0:
            return current.val
        current = current.left  # Move to left subtree

Explanation#

• Reverse Inorder: Traverse right first, then root, then left. Track k and return when k == 0.

Time & Space Complexity#

• Time Complexity: O(h + k), where h is the height and k is the input.
• Space Complexity: O(h) for the stack.

9. Validate a BST with Duplicates#

Problem Statement#

Validate a BST where duplicates are allowed (duplicates must be in the left subtree: left <= root < right).

Approach#

Modify the standard BST validation to allow duplicates in the left subtree. Update the bounds to min_val <= node.val < max_val.

Solution Code#

def is_valid_bst_with_duplicates(root: TreeNode) -> bool:
    def helper(node, min_val, max_val):
        if not node:
            return True
        if not (min_val <= node.val < max_val):
            return False
        return (helper(node.left, min_val, node.val) and 
                helper(node.right, node.val, max_val))
    
    return helper(root, float('-inf'), float('inf'))

Explanation#

• Bounds Adjustment: Allow node.val to be equal to min_val (duplicates in the left subtree) but strictly less than max_val.

Time & Space Complexity#

• Time Complexity: O(n), where n is the number of nodes.
• Space Complexity: O(h) for the recursion stack.

10. Convert Sorted Array to Balanced BST#

Problem Statement#

Given a sorted array, convert it into a height-balanced BST (height difference between left and right subtrees ≤ 1).

Approach#

The middle element of the array is the root (balances the tree). Recursively build left and right subtrees from the left and right subarrays.

Solution Code#

def sorted_array_to_bst(nums: list[int]) -> TreeNode:
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

Explanation#

• Middle Element as Root: Ensures the tree is balanced, as the left and right subarrays will have lengths differing by at most 1.

Time & Space Complexity#

• Time Complexity: O(n), where n is the length of the array (each element is visited once).
• Space Complexity: O(log n) for the recursion stack (balanced BST height).

11. Flatten a BST to a Sorted Doubly Linked List#

Problem Statement#

Flatten a BST into a sorted doubly linked list (inorder traversal order). The left pointer of each node should point to the previous node, and the right pointer to the next node.

Approach#

Use inorder traversal to link nodes. Track the previous node and adjust pointers:

• prev.right = current (link previous to current).
• current.left = prev (link current to previous).

Solution Code#

def flatten_bst_to_dll(root: TreeNode) -> TreeNode:
    prev = None
    head = None
    
    def inorder(node):
        nonlocal prev, head
        if not node:
            return
        inorder(node.left)
        # Link prev and current node
        if prev:
            prev.right = node
            node.left = prev
        else:
            head = node  # First node is head
        prev = node
        inorder(node.right)
    
    inorder(root)
    return head

Explanation#

• Inorder Traversal: Visits nodes in sorted order.
• Linking Nodes: prev tracks the last visited node. For the first node, set head; for others, link prev.right to current and current.left to prev.

Time & Space Complexity#

• Time Complexity: O(n), where n is the number of nodes.
• Space Complexity: O(h) for the recursion stack.

Conclusion#

BST problems are a cornerstone of coding interviews, testing your ability to apply tree properties, recursion, and iterative traversal techniques. By mastering these problems, you’ll gain confidence in solving not just BST-specific questions but also more complex tree-based challenges (e.g., AVL trees, Red-Black trees). Practice with variations (e.g., handling duplicates, skewed trees) to ensure you’re prepared for any interview scenario.

References#

• LeetCode BST Problems
• GeeksforGeeks BST Tutorial
• Introduction to Algorithms (CLRS), Chapter 12: Binary Search Trees.