🌲 Binary Trees

The Family Tree Analogy

A family tree has a clear structure:

• One person at the top (the root)
• Each person can have children below them
• In a binary tree, each person has at most two children (left and right)

Binary trees organize data hierarchically, with each node having at most two children - a left child and a right child.

Binary Tree Structure

        1          ← Root (top of tree)
       / \
      2   3        ← Level 1
     / \   \
    4   5   6      ← Level 2 (Leaves: no children)

Terminology

Root:     The topmost node (1)
Parent:   Node above (2 is parent of 4, 5)
Child:    Node below (4, 5 are children of 2)
Sibling:  Nodes with same parent (4, 5 are siblings)
Leaf:     Node with no children (4, 5, 6)
Height:   Longest path from root to leaf (2 in this case)
Depth:    Distance from root (node 4 has depth 2)

Types of Binary Trees

Full Binary Tree

Every node has 0 or 2 children (but not 1):

      1
     / \
    2   3
   / \
  4   5

Complete Binary Tree

All levels filled except possibly last, which fills left to right:

      1
     / \
    2   3
   / \
  4   5

Perfect Binary Tree

All levels completely filled:

      1
     / \
    2   3
   / \ / \
  4  5 6  7

Binary Search Tree (BST)

Left children < parent < right children:

      5
     / \
    3   7     3 < 5 < 7
   / \ / \
  1  4 6  9   All follow the rule!

Tree Traversals

How to Visit Every Node

There are four main ways to traverse a tree:

Depth-First (uses stack/recursion):

1. Preorder: Root → Left → Right
2. Inorder: Left → Root → Right
3. Postorder: Left → Right → Root

Breadth-First (uses queue): 4. Level-order: Level by level, left to right

Visual Example

        1
       / \
      2   3
     / \
    4   5

Inorder on BST

BST:
      5
     / \
    3   7
   / \
  1   4

Inorder: 1, 3, 4, 5, 7 ← Sorted!

This is why BSTs are useful for maintaining sorted data.

Binary Search Tree (BST) Operations

Search: O(log n) average

Find 4:
      5         5 > 4, go left
     / \
    3   7       3 < 4, go right
   / \
  1   4  ← Found!

Insert: O(log n) average

Insert 4:
      5         5 > 4, go left
     / \
    3   7       3 < 4, go right
   / \
  1   _         Insert as right child of 3

Delete: O(log n) average

Three cases:

1. Leaf node: Just remove it
2. One child: Replace with child
3. Two children: Replace with inorder successor (smallest in right subtree)

BST Degeneracy

If you insert sorted data, BST becomes a linked list:

Insert: 1, 2, 3, 4, 5

    1
     \
      2
       \
        3
         \
          4
           \
            5

Height = n, operations become O(n)!
Solution: Use balanced trees (AVL, Red-Black)

Classic Binary Tree Problems

1. Maximum Depth

        3
       / \
      9  20
         / \
        15  7

Max depth = 3 (root to 15 or 7)

Approach: max(leftDepth, rightDepth) + 1

2. Check if Balanced

Balanced: heights of left and right subtrees differ by at most 1

        3
       / \
      9  20    ← Balanced (heights 1 and 2)
         / \
        15  7

3. Lowest Common Ancestor

Find LCA of 4 and 5:
        3
       / \
      5   1
     / \
    6   2
       / \
      7   4

LCA = 5 (lowest node that is ancestor of both)

4. Validate BST

Check if tree follows BST property:
Every node must be in valid range!

      5
     / \
    3   7       Valid: 3 in (-∞, 5), 7 in (5, ∞)
   / \
  1   6         Invalid! 6 should be < 3, but it's not

5. Level Order Traversal

        3
       / \
      9  20
         / \
        15  7

Result: [[3], [9, 20], [15, 7]]

Binary Tree vs Other Structures

Common Mistakes

1. Ignoring Edge Cases

Handle: empty tree, single node, unbalanced trees.

2. Confusing Height and Depth

Height: from node down to deepest leaf. Depth: from root down to node.

3. Not Considering Degeneracy

BST can become O(n) if unbalanced. Use balanced variants for guarantees.

4. Wrong Traversal Order

Preorder, inorder, postorder are different! Know which you need.

FAQ

Q: When to use binary tree vs binary search tree?

Binary tree: just hierarchical structure. BST: when you need sorted operations (search, min, max).

Q: What's a balanced tree?

A tree where heights of subtrees don't differ much, ensuring O(log n) operations. Examples: AVL, Red-Black trees.

Q: Recursion vs iteration for tree traversal?

Recursion is cleaner and more intuitive. Iteration (with stack) avoids stack overflow for deep trees.

Q: How do I know which traversal to use?

Preorder: top-down processing Inorder: sorted order (BST) Postorder: bottom-up processing Level-order: breadth-first, by level

Summary

Binary trees are hierarchical structures where each node has at most two children.

Key Takeaways:

• Each node has left and right children (or null)
• BST: left < parent < right (enables O(log n) search)
• Four traversals: preorder, inorder, postorder, level-order
• Inorder on BST gives sorted order
• Watch for degeneracy - use balanced trees
• Foundation for heaps, expression trees, and more

Trees are everywhere - from file systems to databases!