Binary Search Trees

Ordered Trees for Efficient Search

A Binary Search Tree (BST) is a powerful 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.
There must be no duplicate keys.

This structure allows for fast lookup, addition, and removal of data items. On average, these operations take O(log n) time, where n is the number of nodes in the tree. However, the worst-case time complexity can be O(n) if the tree becomes unbalanced.

Binary Search Tree Structure

Note: All values in the left subtree of 8 are smaller, and all in the right are larger.

1. Core Operations

Search

To search for a value, you start at the root. If the value is less than the root, you go to the left child; if it's greater, you go to the right child. You repeat this process until you find the value or reach a null pointer.

Time: O(h) | Space: O(h) for recursive (O(1) for iterative), where h is the height.

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        curr = root
        while curr:
            if val < curr.val:
                curr = curr.left
            elif val > curr.val:
                curr = curr.right
            else:
                return curr
        return None

Insertion

Insertion is similar to searching. You traverse the tree to find the correct position for the new value and then insert a new node there.

Time: O(h) | Space: O(h) or O(1)

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        
        curr = root
        while True:
            if val > curr.val:
                if not curr.right:
                    curr.right = TreeNode(val)
                    return root
                curr = curr.right
            else:
                if not curr.left:
                    curr.left = TreeNode(val)
                    return root
                curr = curr.left

Deletion

Deletion is the most complex operation. There are three cases for the node to be deleted:

Node is a leaf: Simply remove the node.
Node has one child: Replace the node with its child.
Node has two children: Find the node's "in-order successor" (the smallest value in its right subtree). Copy the value of the successor to the node, and then recursively delete the successor.

Time: O(h) | Space: O(h) or O(1)

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else: # Found the node
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                # Find the in-order successor (min value in right subtree)
                min_node = root.right
                while min_node.left:
                    min_node = min_node.left
                root.val = min_node.val
                root.right = self.deleteNode(root.right, root.val)
        return root

2. Classic Problems

Validate Binary Search Tree

This problem tests your understanding of the BST property. It's not enough to check node.left < node < node.right. You must ensure all nodes in the left subtree are smaller and all in the right are larger. This is done by passing down valid range constraints (min and max) during the traversal.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, low=-float('inf'), high=float('inf')):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))
        
        return validate(root)

Kth Smallest Element in a BST

The key insight here is that an in-order traversal of a BST visits the nodes in sorted ascending order. You can perform an in-order traversal and stop once you have visited k elements.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root
        
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            
            curr = curr.right

Construct Binary Search Tree from Preorder Traversal

This problem leverages the properties of both preorder traversal and BSTs. The first element of a preorder traversal is always the root. The subsequent elements are then partitioned into those that belong in the left subtree (smaller than the root) and those that belong in the right subtree (larger than the root). You can solve this recursively.

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        self.i = 0
        def build(bound=float('inf')):
            if self.i == len(preorder) or preorder[self.i] > bound:
                return None
            
            node = TreeNode(preorder[self.i])
            self.i += 1
            node.left = build(node.val)
            node.right = build(bound)
            return node
            
        return build()