Tree Fundamentals

Binary Trees: Tree Fundamentals 🌳

Imagine a magical family tree where everyone has at most two children. That’s a Binary Tree!

The Big Picture

Think of a Binary Tree like an upside-down tree in a park. The roots are at the top (we call it the root node), and branches grow downward. Each branch can split into at most two smaller branches.

Why do we care? Binary Trees help computers organize and find data super fast—like finding a name in a phone book without checking every single page!

1. Binary Tree Fundamentals

What IS a Binary Tree?

Picture a family where every parent can have at most 2 children—a left child and a right child. That’s it!

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

Real-Life Example:

       📦 CEO (Root)
       /      \
    📦 CTO    📦 CFO
    /    \        \
 📦 Dev  📦 QA   📦 Accountant

Key Terms (Simple Definitions)

Building Your First Tree

# Create nodes
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

#     1
#    / \
#   2   3
#  / \
# 4   5

2. Tree Traversal Techniques

The Big Idea

Imagine you’re visiting every room in a house. Traversal means visiting every node in the tree—but in what ORDER?

There are 3 main ways to walk through a tree:

2.1 Inorder Traversal (Left → Root → Right)

Story: Visit left child first, then yourself, then right child.

def inorder(node):
    if not node:
        return
    inorder(node.left)   # Go left
    print(node.val)      # Visit me
    inorder(node.right)  # Go right

Example Tree:

    2
   / \
  1   3

Inorder Result: 1, 2, 3 ✨ (Sorted order for BST!)

2.2 Preorder Traversal (Root → Left → Right)

Story: Visit yourself FIRST, then explore children.

def preorder(node):
    if not node:
        return
    print(node.val)       # Visit me first!
    preorder(node.left)   # Then left
    preorder(node.right)  # Then right

Same Tree Result: 2, 1, 3

2.3 Postorder Traversal (Left → Right → Root)

Story: Save the best (yourself) for LAST!

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)       # Visit me last!

Same Tree Result: 1, 3, 2

2.4 Level Order (BFS)

Story: Visit floor by floor, like scanning a building.

from collections import deque

def level_order(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

Result: 2, 1, 3 (top to bottom, left to right)

3. Tree Height and Depth

What’s the Difference?

Think of it like a building:

• Depth = Which floor am I on? (counting from roof)
• Height = How many floors below me?

       1        ← Depth 0, Height 2
      / \
     2   3      ← Depth 1, Height 1
    /
   4            ← Depth 2, Height 0 (leaf!)

Calculate Height

def height(node):
    if not node:
        return -1  # Empty tree
    left_h = height(node.left)
    right_h = height(node.right)
    return 1 + max(left_h, right_h)

Example: For the tree above, height(root) = 2

4. Tree Diameter

The Big Question

Diameter = The longest path between ANY two nodes in the tree.

Key Insight: The longest path might NOT go through the root!

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

Longest path: 6 → 4 → 2 → 5 → 7 = 4 edges

Calculate Diameter

def diameter(root):
    result = [0]  # Store max diameter

    def height(node):
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        # Update diameter: path through node
        result[0] = max(result[0], left + right)
        return 1 + max(left, right)

    height(root)
    return result[0]

Time: O(n) — we visit each node once!

5. Binary Tree Maximum Path Sum

The Challenge

Find the path with the maximum sum of node values. The path can start and end at ANY node!

Example:

      -10
      /  \
     9    20
         /  \
        15   7

Best Path: 15 → 20 → 7 = 42

The Strategy

At each node, decide:

1. Should I extend the path upward?
2. Is the path through me the best so far?

def max_path_sum(root):
    result = [float('-inf')]

    def helper(node):
        if not node:
            return 0
        # Only take positive contributions
        left = max(0, helper(node.left))
        right = max(0, helper(node.right))
        # Path through current node
        current_sum = node.val + left + right
        result[0] = max(result[0], current_sum)
        # Return max path extending upward
        return node.val + max(left, right)

    helper(root)
    return result[0]

Key Trick: Use max(0, ...) to ignore negative paths!

6. Lowest Common Ancestor (LCA)

What is LCA?

The Lowest Common Ancestor of two nodes is the deepest node that has BOTH nodes as descendants.

Think of it like: “What’s the first meeting point if two cousins trace back their family tree?”

        3
       / \
      5   1
     / \ / \
    6  2 0  8

• LCA of 6 and 2? → 5 (parent of both)
• LCA of 6 and 8? → 3 (root is the meeting point)
• LCA of 5 and 1? → 3

Find LCA

def lowest_common_ancestor(root, p, q):
    if not root:
        return None
    if root == p or root == q:
        return root

    left = lowest_common_ancestor(
        root.left, p, q
    )
    right = lowest_common_ancestor(
        root.right, p, q
    )

    # If both sides found something
    if left and right:
        return root
    # Return whichever side found it
    return left if left else right

Logic: If p is in left subtree and q is in right subtree, the current node is the LCA!

7. Path Sum Problems

Problem 7.1: Does a Path Exist with Target Sum?

Question: Is there a root-to-leaf path where node values add up to target?

        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1

Target = 22 → Path: 5 → 4 → 11 → 2 ✅

def has_path_sum(root, target):
    if not root:
        return False
    # Check if leaf with exact sum
    if not root.left and not root.right:
        return root.val == target
    # Try both children with reduced target
    return (
        has_path_sum(root.left, target - root.val)
        or
        has_path_sum(root.right, target - root.val)
    )

Problem 7.2: Find ALL Paths with Target Sum

def path_sum(root, target):
    result = []

    def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        # If leaf and sum matches
        if not node.left and not node.right:
            if remaining == node.val:
                result.append(list(path))
        else:
            dfs(node.left, remaining - node.val, path)
            dfs(node.right, remaining - node.val, path)
        path.pop()  # Backtrack!

    dfs(root, target, [])
    return result

Problem 7.3: Path Sum III (Any Starting Point)

Count paths that sum to target—they can start from ANY node!

def path_sum_iii(root, target):
    def count_paths(node, curr_sum):
        if not node:
            return 0
        curr_sum += node.val
        # Paths ending here with target sum
        count = prefix_sums.get(
            curr_sum - target, 0
        )
        prefix_sums[curr_sum] = (
            prefix_sums.get(curr_sum, 0) + 1
        )
        # Explore children
        count += count_paths(node.left, curr_sum)
        count += count_paths(node.right, curr_sum)
        # Backtrack
        prefix_sums[curr_sum] -= 1
        return count

    prefix_sums = {0: 1}
    return count_paths(root, 0)

Magic Trick: Use a prefix sum hashmap to track all possible starting points!

Summary Diagram

graph TD
    A["Binary Tree Fundamentals"] --> B["Traversals"]
    A --> C["Height & Depth"]
    A --> D["Diameter"]
    A --> E["Max Path Sum"]
    A --> F["LCA"]
    A --> G["Path Sum Problems"]

    B --> B1["Inorder: L-Root-R"]
    B --> B2["Preorder: Root-L-R"]
    B --> B3["Postorder: L-R-Root"]
    B --> B4["Level Order: BFS"]

    G --> G1["Has Path Sum?"]
    G --> G2["All Paths"]
    G --> G3["Any Start Point"]

Quick Reference Table

h = height of tree (log n for balanced, n for skewed)

You’ve Got This! 🎉

Binary trees might seem complex at first, but they’re just upside-down trees with simple rules:

• Each node has at most 2 children
• We can visit nodes in different orders (traversals)
• Most problems use recursion to break down the tree

Practice these patterns, and soon you’ll see trees everywhere in computer science—databases, file systems, decision making, and more!

Next Step: Try implementing each algorithm yourself. Start with the simpler ones (traversals, height) and work your way up to path sum problems. You’ve got this! 🚀