Report Content

Binary Search Trees: Operations, Balancing & Applications

Master BST operations, balancing techniques, and real-world applications. This tutorial covers insertion, deletion, traversal, and self-balancing trees with implementation examples.

BST Usage in Systems (2023)

Database Indexing (40%)

Search Algorithms (30%)

Memory Management (20%)

Other (10%)

1. BST Fundamentals

Definition

A Binary Search Tree (BST) is a binary tree where:

All values in the left subtree are smaller than the node.
All values in the right subtree are greater than the node.

                   Core Properties:
        Ordering: Left subtree ≤ Node ≤ Right subtree
No Duplicates: Typically stores unique values
Efficiency: O(h) operations, where h = tree height

How It Works

Search

Start at the root node.
If target == node → return found.
If target < node → go left child.
If target > node → go right child.
Repeat until found or null.

Insert

Start at the root node.
If value < node → move left.
If value > node → move right.
Insert into empty position.

Delete

Find the node to remove.
Leaf node → remove directly.
One child → replace with child.
Two children → replace with inorder successor.

Time Complexities:

Operation	Average Case	Worst Case (Unbalanced)	Balanced Tree
Search	O(log n)	O(n)	O(log n)
Insertion	O(log n)	O(n)	O(log n)
Deletion	O(log n)	O(n)	O(log n)
Traversal	O(n)	O(n)	O(n)

Node Implementation:

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

class BSTNode {

    int value;
    BSTNode left;
    BSTNode right;

    BSTNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

class BinarySearchTree {

    BSTNode root;

    BinarySearchTree() {
        root = null;
    }
}

#include <iostream>
using namespace std;

class BSTNode {

public:
    int value;
    BSTNode* left;
    BSTNode* right;

    BSTNode(int val) {
        value = val;
        left = nullptr;
        right = nullptr;
    }
};

class BinarySearchTree {

public:
    BSTNode* root;

    BinarySearchTree() {
        root = nullptr;
    }
};

2. Core BST Operations

Essential Methods:

Insertion

def insert(self, value):

    new_node = BSTNode(value)

    if self.root is None:
        self.root = new_node
        return

    current = self.root

    while True:

        if value < current.value:

            if current.left is None:
                current.left = new_node
                break

            current = current.left

        elif value > current.value:

            if current.right is None:
                current.right = new_node
                break

            current = current.right

        else:
            break

insert(value) {

  const newNode = new BSTNode(value);

  if (!this.root) {
    this.root = newNode;
    return;
  }

  let current = this.root;

  while (true) {

    if (value < current.value) {

      if (!current.left) {
        current.left = newNode;
        newNode.parent = current;
        break;
      }

      current = current.left;

    } else if (value > current.value) {

      if (!current.right) {
        current.right = newNode;
        newNode.parent = current;
        break;
      }

      current = current.right;

    } else {
      break;
    }
  }
}

public void insert(int value) {

    BSTNode newNode = new BSTNode(value);

    if (root == null) {
        root = newNode;
        return;
    }

    BSTNode current = root;

    while (true) {

        if (value < current.value) {

            if (current.left == null) {
                current.left = newNode;
                break;
            }

            current = current.left;

        } else if (value > current.value) {

            if (current.right == null) {
                current.right = newNode;
                break;
            }

            current = current.right;

        } else {
            break;
        }
    }
}

void insert(int value) {

    BSTNode* newNode = new BSTNode(value);

    if (root == nullptr) {
        root = newNode;
        return;
    }

    BSTNode* current = root;

    while (true) {

        if (value < current->value) {

            if (current->left == nullptr) {
                current->left = newNode;
                break;
            }

            current = current->left;

        } else if (value > current->value) {

            if (current->right == nullptr) {
                current->right = newNode;
                break;
            }

            current = current->right;

        } else {
            break;
        }
    }
}

Deletion (3 Cases)

def delete(self, value):
    node, parent = self._find_with_parent(value)
    if not node:
        return False

    # Case 1: No children
    if not node.left and not node.right:
        self._replace_child(parent, node, None)

    # Case 2: One child
    elif not node.left or not node.right:
        child = node.left or node.right
        self._replace_child(parent, node, child)

    # Case 3: Two children
    else:
        successor = self._find_min(node.right)
        node.value = successor.value
        self.delete(successor.value)

    return True

def _find_min(self, node):
    while node.left:
        node = node.left
    return node

def _replace_child(self, parent, old_child, new_child):
    if not parent:
        self.root = new_child
    elif parent.left == old_child:
        parent.left = new_child
    else:
        parent.right = new_child

delete(value) {
  const [node, parent] = this._findWithParent(value);
  if (!node) return false;

  // Case 1: No children
  if (!node.left && !node.right) {
    this._replaceChild(parent, node, null);
  }
  // Case 2: One child
  else if (!node.left || !node.right) {
    const child = node.left || node.right;
    this._replaceChild(parent, node, child);
  }
  // Case 3: Two children
  else {
    const successor = this._findMin(node.right);
    node.value = successor.value;
    this.delete(successor.value);
  }
  return true;
}

_findMin(node) {
  while (node.left) node = node.left;
  return node;
}

public boolean delete(int value) {
    Node[] result = findWithParent(value);
    Node node = result[0];
    Node parent = result[1];
    
    if (node == null) return false;

    // Case 1: No children
    if (node.left == null && node.right == null) {
        replaceChild(parent, node, null);
    }
    // Case 2: One child
    else if (node.left == null || node.right == null) {
        Node child = (node.left != null) ? node.left : node.right;
        replaceChild(parent, node, child);
    }
    // Case 3: Two children
    else {
        Node successor = findMin(node.right);
        node.value = successor.value;
        delete(successor.value);
    }
    return true;
}

private Node findMin(Node node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

private void replaceChild(Node parent, Node oldChild, Node newChild) {
    if (parent == null) {
        root = newChild;
    } else if (parent.left == oldChild) {
        parent.left = newChild;
    } else {
        parent.right = newChild;
    }
}

private Node[] findWithParent(int value) {
    Node parent = null;
    Node current = root;
    
    while (current != null) {
        if (value == current.value) {
            return new Node[]{current, parent};
        }
        parent = current;
        current = (value < current.value) ? current.left : current.right;
    }
    return new Node[]{null, null};
}

bool deleteValue(int value) {
    auto [node, parent] = findWithParent(value);
    if (!node) return false;

    // Case 1: No children
    if (!node->left && !node->right) {
        replaceChild(parent, node, nullptr);
    }
    // Case 2: One child
    else if (!node->left || !node->right) {
        Node* child = node->left ? node->left : node->right;
        replaceChild(parent, node, child);
    }
    // Case 3: Two children
    else {
        Node* successor = findMin(node->right);
        node->value = successor->value;
        deleteValue(successor->value);
    }
    return true;
}

Node* findMin(Node* node) {
    while (node->left) {
        node = node->left;
    }
    return node;
}

void replaceChild(Node* parent, Node* oldChild, Node* newChild) {
    if (!parent) {
        root = newChild;
    } else if (parent->left == oldChild) {
        parent->left = newChild;
    } else {
        parent->right = newChild;
    }
}

pair<Node*, Node*> findWithParent(int value) {
    Node* parent = nullptr;
    Node* current = root;
    
    while (current) {
        if (value == current->value) {
            return {current, parent};
        }
        parent = current;
        current = (value < current->value) ? current->left : current->right;
    }
    return {nullptr, nullptr};
}

Search Techniques:

Iterative Search: Efficient O(h) implementation
Recursive Search: Cleaner code but uses call stack
Range Queries: Find all values between [x, y]
Successor/Predecessor: In-order traversal helpers

3. Balancing BSTs

Self-Balancing Variants:

AVL Trees

Height-balanced with rotations

class AVLTree(BinarySearchTree):
    def insert(self, value):
        super().insert(value)
        self._balance(self.root)

    def _balance(self, node):
        if not node:
            return
        
        balance_factor = self._get_balance_factor(node)
        
        # Left heavy
        if balance_factor > 1:
            if self._get_balance_factor(node.left) >= 0:
                self._rotate_right(node)
            else:
                self._rotate_left(node.left)
                self._rotate_right(node)
        
        # Right heavy
        elif balance_factor < -1:
            if self._get_balance_factor(node.right) <= 0:
                self._rotate_left(node)
            else:
                self._rotate_right(node.right)
                self._rotate_left(node)
        
        self._balance(node.left)
        self._balance(node.right)
    
    def _get_balance_factor(self, node):
        if not node:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)
    
    def _get_height(self, node):
        if not node:
            return 0
        return 1 + max(self._get_height(node.left), self._get_height(node.right))
    
    def _rotate_right(self, node):
        left_child = node.left
        node.left = left_child.right
        left_child.right = node
        return left_child
    
    def _rotate_left(self, node):
        right_child = node.right
        node.right = right_child.left
        right_child.left = node
        return right_child

class AVLTree extends BinarySearchTree {
  insert(value) {
    super.insert(value);
    this._balance(this.root);
  }

  _balance(node) {
    if (!node) return;
    const balanceFactor = this._getBalanceFactor(node);
    
    // Left heavy
    if (balanceFactor > 1) {
      if (this._getBalanceFactor(node.left) >= 0) {
        this._rotateRight(node);
      } else {
        this._rotateLeft(node.left);
        this._rotateRight(node);
      }
    }
    // Right heavy
    else if (balanceFactor < -1) {
      if (this._getBalanceFactor(node.right) <= 0) {
        this._rotateLeft(node);
      } else {
        this._rotateRight(node.right);
        this._rotateLeft(node);
      }
    }
    
    this._balance(node.left);
    this._balance(node.right);
  }
}

public class AVLTree extends BinarySearchTree {
    
    @Override
    public void insert(int value) {
        super.insert(value);
        balance(root);
    }
    
    private void balance(AVLNode node) {
        if (node == null) return;
        
        int balanceFactor = getBalanceFactor(node);
        
        // Left heavy
        if (balanceFactor > 1) {
            if (getBalanceFactor(node.left) >= 0) {
                rotateRight(node);
            } else {
                rotateLeft(node.left);
                rotateRight(node);
            }
        }
        // Right heavy
        else if (balanceFactor < -1) {
            if (getBalanceFactor(node.right) <= 0) {
                rotateLeft(node);
            } else {
                rotateRight(node.right);
                rotateLeft(node);
            }
        }
        
        balance(node.left);
        balance(node.right);
    }
    
    private int getBalanceFactor(AVLNode node) {
        if (node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }
    
    private int getHeight(AVLNode node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
    
    private AVLNode rotateRight(AVLNode node) {
        AVLNode leftChild = node.left;
        node.left = leftChild.right;
        leftChild.right = node;
        return leftChild;
    }
    
    private AVLNode rotateLeft(AVLNode node) {
        AVLNode rightChild = node.right;
        node.right = rightChild.left;
        rightChild.left = node;
        return rightChild;
    }
}

class AVLTree : public BinarySearchTree {
public:
    void insert(int value) override {
        BinarySearchTree::insert(value);
        balance(root);
    }

private:
    void balance(Node* node) {
        if (!node) return;
        
        int balanceFactor = getBalanceFactor(node);
        
        // Left heavy
        if (balanceFactor > 1) {
            if (getBalanceFactor(node->left) >= 0) {
                rotateRight(node);
            } else {
                rotateLeft(node->left);
                rotateRight(node);
            }
        }
        // Right heavy
        else if (balanceFactor < -1) {
            if (getBalanceFactor(node->right) <= 0) {
                rotateLeft(node);
            } else {
                rotateRight(node->right);
                rotateLeft(node);
            }
        }
        
        balance(node->left);
        balance(node->right);
    }
    
    int getBalanceFactor(Node* node) {
        if (!node) return 0;
        return getHeight(node->left) - getHeight(node->right);
    }
    
    int getHeight(Node* node) {
        if (!node) return 0;
        return 1 + std::max(getHeight(node->left), getHeight(node->right));
    }
    
    Node* rotateRight(Node* node) {
        Node* leftChild = node->left;
        node->left = leftChild->right;
        leftChild->right = node;
        return leftChild;
    }
    
    Node* rotateLeft(Node* node) {
        Node* rightChild = node->right;
        node->right = rightChild->left;
        rightChild->left = node;
        return rightChild;
    }
};

Red-Black Trees

Color-coded nodes with rules

class RedBlackTree(BinarySearchTree):

    def insert(self, value):

        new_node = super().insert(value)

        new_node.color = "RED"

        self._fix_insert_violation(new_node)

    def _fix_insert_violation(self, node):

        while node != self.root and node.parent.color == "RED":

            # Complex recoloring and rotation logic
            pass

        self.root.color = "BLACK"

class RedBlackTree extends BinarySearchTree {

  insert(value) {

    const newNode = super.insert(value);

    newNode.color = 'RED';

    this._fixInsertViolation(newNode);
  }

  _fixInsertViolation(node) {

    while (
      node !== this.root &&
      node.parent.color === 'RED'
    ) {

      // Complex recoloring and rotation logic
    }

    this.root.color = 'BLACK';
  }
}

class RedBlackTree extends BinarySearchTree {

    public void insert(int value) {

        BSTNode newNode = super.insert(value);

        newNode.color = "RED";

        fixInsertViolation(newNode);
    }

    private void fixInsertViolation(BSTNode node) {

        while (
            node != root &&
            node.parent.color.equals("RED")
        ) {

            // Complex recoloring and rotation logic
        }

        root.color = "BLACK";
    }
}

class RedBlackTree : public BinarySearchTree {

public:

    void insert(int value) {

        BSTNode* newNode = BinarySearchTree::insert(value);

        newNode->color = "RED";

        fixInsertViolation(newNode);
    }

private:

    void fixInsertViolation(BSTNode* node) {

        while (
            node != root &&
            node->parent->color == "RED"
        ) {

            // Complex recoloring and rotation logic
        }

        root->color = "BLACK";
    }
};

Balancing Operations:

Left Rotation: Pivot around right child
Right Rotation: Pivot around left child
Left-Right Rotation: Double rotation
Right-Left Rotation: Mirror of above

BST Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Validate BST	In-order traversal check	O(n)
Kth Smallest	In-order traversal with count	O(k)
Lowest Common Ancestor	Utilize BST properties	O(h)
Range Sum	Modified traversal	O(k)

4. Advanced BST Concepts

Threaded BST

Optimized for in-order traversal

class ThreadedBSTNode(BSTNode):

    def __init__(self, value):

        super().__init__(value)

        self.left_thread = False
        self.right_thread = False

class ThreadedBSTNode extends BSTNode {

  constructor(value) {

    super(value);

    this.leftThread = false;
    this.rightThread = false;
  }
}

class ThreadedBSTNode extends BSTNode {

    boolean leftThread;
    boolean rightThread;

    ThreadedBSTNode(int value) {

        super(value);

        leftThread = false;
        rightThread = false;
    }
}

class ThreadedBSTNode : public BSTNode {

public:

    bool leftThread;
    bool rightThread;

    ThreadedBSTNode(int value)
        : BSTNode(value) {

        leftThread = false;
        rightThread = false;
    }
};

B-Tree Variants

Optimized for disk storage

class BTreeNode:

    def __init__(self, order):

        self.keys = []
        self.children = []
        self.order = order
        self.is_leaf = True

class BTreeNode {

  constructor(order) {

    this.keys = [];
    this.children = [];
    this.order = order;
    this.isLeaf = true;
  }
}

class BTreeNode {

    int order;
    boolean isLeaf;

    ArrayList<Integer> keys;
    ArrayList<BTreeNode> children;

    BTreeNode(int order) {

        this.order = order;

        keys = new ArrayList<>();
        children = new ArrayList<>();

        isLeaf = true;
    }
}

#include <vector>
using namespace std;

class BTreeNode {

public:

    vector<int> keys;
    vector<BTreeNode*> children;

    int order;
    bool isLeaf;

    BTreeNode(int order) {

        this->order = order;

        isLeaf = true;
    }
};

Augmented BST

Additional node metadata

class AugmentedBSTNode(BSTNode):
    def __init__(self, value):
        super().__init__(value)
        self.size = 1      # Subtree node count
        self.sum = value   # Subtree sum

    class AugmentedBSTNode extends BSTNode {
  constructor(value) {
    super(value);
    this.size = 1; // Subtree node count
    this.sum = value; // Subtree sum
  }
}

public class AugmentedBSTNode extends BSTNode {
    public int size;   // Subtree node count
    public int sum;    // Subtree sum
    
    public AugmentedBSTNode(int value) {
        super(value);
        this.size = 1;
        this.sum = value;
    }
}

class AugmentedBSTNode : public BSTNode {
public:
    int size;  // Subtree node count
    int sum;   // Subtree sum
    
    AugmentedBSTNode(int value) : BSTNode(value) {
        size = 1;
        sum = value;
    }
};

BST Problem-Solving Checklist

Verify BST property maintenance

Consider balance factor for performance

Handle all deletion cases (0, 1, 2 children)

Utilize in-order traversal for sorted output

DSA Expert Insight: BST problems appear in 35% of technical interviews. Mastering both basic operations and balancing techniques is crucial for efficient search and retrieval problems.

You need to be logged in to participate in this discussion.