Binary Trees

1 min read•1 page

A Binary Tree is a tree structure where every node has at most two children, referred to as the left child and the right child.

BinaryNode(key, value):

1. Key: The value used to sort and search the tree. 2. Left Child: Node with key less than parent key (in Binary Search Trees). 3. Right Child: Node with key greater than parent key.

python

1class BinaryNode:
2    def __init__(self, key, value=None):
3        self.key = key         # Search key / index value
4        self.value = value     # Associated data payload
5        self.left = None       # Reference to left child (BinaryNode)
6        self.right = None      # Reference to right child (BinaryNode)

1 min read•1 page

To build a Binary Search Tree (BST), we insert keys recursively. At every node, we check if the new key is smaller (routing it left) or larger (routing it right), until an empty slot is found.

Insert(node, key):

1. Key < Node: Recurse into the left subtree. 2. Key > Node: Recurse into the right subtree. 3. Base Case: Create a new node when a null link is encountered.

python

1def insert(node, key, value=None) -> BinaryNode:
2    # If the tree is empty, return a new node
3    if node is None:
4        return BinaryNode(key, value)
5        
6    # Otherwise, recur down the tree
7    if key < node.key:
8        node.left = insert(node.left, key, value)
9    elif key > node.key:
10        node.right = insert(node.right, key, value)
11        
12    return node

Key to Insert

35.00

2 min read•1 page

Binary search trees allow fast lookup operations. At each node, we compare the target key. Since we discard half the remaining tree at each comparison, the search takes O(log N) time.

Search(node, target_key):

1. Equal: Target found, return node. 2. Smaller: Search left subtree recursively. 3. Larger: Search right subtree recursively.

python

1def search(node, target_key) -> BinaryNode:
2    # Base Cases: root is null or key is present at root
3    if node is None or node.key == target_key:
4        return node
5        
6    # Target is smaller than root's key
7    if target_key < node.key:
8        return search(node.left, target_key)
9        
10    # Target is greater than root's key
11    return search(node.right, target_key)

Target Key to Search

40.00

2 min read•1 page

Traversal means visiting all nodes of a tree in a specific order. For binary trees, we have three standard depth-first search (DFS) traversal orderings.

Traverse(node, order):

1. Pre-order (NLR): Visit Node, then Left, then Right. 2. In-order (LNR): Visit Left, then Node, then Right. Output is sorted for BSTs! 3. Post-order (LRN): Visit Left, then Right, then Node. Used to delete trees.

python

1def traverse(node, order_type="inorder"):
2    if node is None:
3        return
4        
5    if order_type == "preorder":
6        print(node.key)          # Visit Root
7        traverse(node.left)       # Left child
8        traverse(node.right)      # Right child
9        
10    elif order_type == "inorder":
11        traverse(node.left)       # Left child
12        print(node.key)          # Visit Root
13        traverse(node.right)      # Right child
14        
15    elif order_type == "postorder":
16        traverse(node.left)       # Left child
17        traverse(node.right)      # Right child
18        print(node.key)          # Visit Root

Traversal Type (0: Pre, 1: In, 2: Post)

0.00

Traversal Progress Step

0.00

2 min read•1 page

Deleting a node in a BST (Hibbard Deletion) must preserve the sorted property. We handle three cases: leaves (remove node), single-child nodes (link child to parent), and two-children nodes (replace with inorder successor).

Delete(root, key):

1. Leaf Node: Simply remove the node. 2. One Child: Replace the node with its child. 3. Two Children: Replace with the inorder successor (smallest node in the right subtree) and delete the successor.

python

1def delete_node(root, key) -> BinaryNode:
2    if root is None:
3        return root
4
5    # 1. Recur down the tree
6    if key < root.key:
7        root.left = delete_node(root.left, key)
8    elif key > root.key:
9        root.right = delete_node(root.right, key)
10    else:
11        # Node with only one child or no child
12        if root.left is None:
13            return root.right
14        elif root.right is None:
15            return root.left
16
17        # Node with two children: get inorder successor
18        temp = get_min_value_node(root.right)
19        root.key = temp.key
20        # Delete inorder successor
21        root.right = delete_node(root.right, temp.key)
22
23    return root

Key to Delete

30.00

1 min read•1 page

Self-balancing trees (like AVL or Red-Black trees) perform local rotations to maintain a maximum height of $O(\log N)$. If a node becomes unbalanced (height difference > 1), we rotate nodes to restore balance.

Left Rotation (z):

1. z: The unbalanced root node. 2. y: The right child of z, which becomes the new parent. 3. Re-link: z becomes the left child of y. y's former left subtree becomes the right child of z.

python

1def rotate_left(z) -> BinaryNode:
2    y = z.right
3    T2 = y.left
4
5    # Perform rotation
6    y.left = z
7    z.right = T2
8
9    # Update heights
10    z.height = 1 + max(get_height(z.left), get_height(z.right))
11    y.height = 1 + max(get_height(y.left), get_height(y.right))
12
13    return y  # New root

Rotation Progress

0.00

1 min read•1 page

Breadth-First Search (BFS) or Level-Order Traversal visits nodes level-by-level, starting from the root and going left-to-right. We implement it using a First-In-First-Out (FIFO) queue.

LevelOrder(root):

1. Queue initialization: Push root node into a queue. 2. Loop: Dequeue a node, visit it, then enqueue its left and right children. 3. Termination: Repeat until the queue is empty.

python

1def level_order(root) -> list:
2    if root is None:
3        return []
4
5    result = []
6    queue = [root] # FIFO queue
7
8    while queue:
9        node = queue.pop(0) # Dequeue
10        result.append(node.key)
11
12        # Enqueue children
13        if node.left:
14            queue.append(node.left)
15        if node.right:
16            queue.append(node.right)
17
18    return result

BFS Traversal Step

0.00