BST Construction

Tags

BST Construction

Category

BST (Binary Search Trees)

Difficulty

Medium

Problem Statement

Implement a Binary Search Tree (BST) class that supports three operations: insertion of a value, removal of a value, and searching for a value. The BST property must be maintained: for any node, all values in its left subtree are strictly less, and all values in its right subtree are greater than or equal to the node's value.

Intuition

A BST organizes data hierarchically so that search, insertion, and deletion can all be performed efficiently by leveraging the ordering property. At each node, we can determine which subtree to explore by comparing the target value with the node's value, effectively halving the search space at each step in a balanced tree.

Approach

Insertion

  1. Start at the root. Compare the value to insert with the current node.
  2. If the value is less than the current node, go left; otherwise, go right.
  3. When a null position is reached, insert the new node there.
  1. Start at the root. Compare the target with the current node.
  2. If equal, return true. If less, go left. If greater, go right.
  3. If a null node is reached, return false.

Removal

  1. Find the node to remove using the search logic.
  2. Three cases:
    • Leaf node: Simply remove it.
    • One child: Replace the node with its child.
    • Two children: Find the in-order successor (smallest value in the right subtree), replace the node's value with it, then recursively remove the successor from the right subtree.

Pseudocode

class BST:
    value, left, right

    function insert(value):
        if value < self.value:
            if self.left is null:
                self.left = new BST(value)
            else:
                self.left.insert(value)
        else:
            if self.right is null:
                self.right = new BST(value)
            else:
                self.right.insert(value)
        return self

    function search(value):
        if value == self.value:
            return true
        else if value < self.value:
            if self.left is null: return false
            return self.left.search(value)
        else:
            if self.right is null: return false
            return self.right.search(value)

    function remove(value, parent = null):
        // Navigate to the node
        if value < self.value:
            if self.left: self.left.remove(value, self)
        else if value > self.value:
            if self.right: self.right.remove(value, self)
        else:
            // Found the node to remove
            if self.left and self.right:
                self.value = self.right.getMinValue()
                self.right.remove(self.value, self)
            else if parent is null:
                // Root node with at most one child
                if self.left:
                    self.value = self.left.value
                    self.right = self.left.right
                    self.left = self.left.left
                else if self.right:
                    self.value = self.right.value
                    self.left = self.right.left
                    self.right = self.right.right
            else if parent.left == self:
                parent.left = self.left or self.right
            else:
                parent.right = self.left or self.right
        return self

    function getMinValue():
        if self.left is null: return self.value
        return self.left.getMinValue()

Time & Space Complexity

  • Time (average): O(log n) for insert, search, and remove in a balanced BST.
  • Time (worst): O(n) for a completely skewed BST (degenerates to a linked list).
  • Space: O(1) for iterative implementations; O(log n) average / O(n) worst for recursive (call stack).

Key Insights

  • Removal is the most complex operation due to the three cases, especially the two-children case.
  • The in-order successor approach for two-children removal maintains the BST property because the successor is the smallest value greater than the removed node.
  • Removing the root node requires special handling since there is no parent to update.
  • Equal values go to the right subtree by convention (this varies by implementation).

Edge Cases

  • Removing the root node when it has 0, 1, or 2 children.
  • Removing a node that does not exist in the tree.
  • Inserting duplicate values.
  • Operations on a single-node tree.
  • Insertions that create a completely skewed tree (sorted input).

Linked mentions