Trees & BST

Tree Basics

• Hierarchical structure: root → children → leaves
• Each node has at most one parent, any number of children
• Binary Tree: each node has at most 2 children (left, right)
• BST: left child < parent < right child, no duplicates

---

BST Operations Complexity

Worst case = completely sorted input → degenerates to a linked list. Fix: use Red-Black tree or AVL tree (self-balancing).

---

BST Node Implementation

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

    def insert(self, val):
        if self.val is None:
            self.val = val; return
        if val == self.val: return         # no duplicates
        if val < self.val:
            if self.left is None: self.left = BSTNode(val)
            else: self.left.insert(val)
        else:
            if self.right is None: self.right = BSTNode(val)
            else: self.right.insert(val)

    def search(self, val):
        if self.val == val: return True
        if val < self.val: return self.left.search(val) if self.left else False
        return self.right.search(val) if self.right else False

    def get_min(self):
        node = self
        while node.left: node = node.left
        return node.val

    def get_max(self):
        node = self
        while node.right: node = node.right
        return node.val

    def delete(self, val):
        if self.val is None: return None
        if val < self.val:
            if self.left: self.left = self.left.delete(val)
        elif val > self.val:
            if self.right: self.right = self.right.delete(val)
        else:
            if not self.right: return self.left
            if not self.left: return self.right
            # Find in-order successor (min of right subtree)
            successor = self.right
            while successor.left: successor = successor.left
            self.val = successor.val
            self.right = self.right.delete(successor.val)
        return self

---

Tree Traversals

# Pre-order: root → left → right  (used for copying tree)
def preorder(node, result=[]):
    if not node: return
    result.append(node.val)
    preorder(node.left, result)
    preorder(node.right, result)
    return result

# In-order: left → root → right  (gives sorted output for BST)
def inorder(node, result=[]):
    if not node: return
    inorder(node.left, result)
    result.append(node.val)
    inorder(node.right, result)
    return result

# Post-order: left → right → root  (used for deleting tree)
def postorder(node, result=[]):
    if not node: return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)
    return result

# Level-order (BFS)
from collections import deque
def level_order(root):
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

---

Red-Black Tree

Self-balancing BST. Guarantees O(log n) for all operations.

Rules:

1. Each node is red or black
2. Root is always black
3. All None leaf nodes are black
4. Red node → both children must be black
5. All paths from a node to its None leaves have the same number of black nodes

Balancing mechanism: Rotations (left/right) — O(1) operation.

For interviews: know the rules and WHY it's needed (standard BST degrades to O(n) on sorted input). Full implementation rarely asked — use Python's sortedcontainers.SortedList in practice.

---

Interview Patterns → see [[Trees]]