Tree Fundamentals

🌳 Binary Trees: Your Family Tree Adventure!

Imagine your family. You have parents, grandparents, and maybe siblings. A binary tree is like a family tree, but with one special rule: every person can have at most 2 children.

Let’s go on an adventure to explore this magical tree!

🏠 Binary Tree Fundamentals

What IS a Binary Tree?

Think of a tree growing upside down! The root is at the TOP (like your great-great-grandparent), and branches go DOWN.

       👴 Root (Grandpa)
      /  \
    👨    👩
   /  \     \
  🧒   👧    👶

Key Terms (Simple Words):

Java Code: Creating a Tree Node

class TreeNode {
    int val;           // The value
    TreeNode left;     // Left child
    TreeNode right;    // Right child

    TreeNode(int val) {
        this.val = val;
    }
}

Example: Build a small tree:

TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
// Tree: 10 with children 5 and 15

🚶 Tree Traversal Techniques

The Grand Tour of Your Tree!

Imagine you want to visit every person in your family tree. But in what ORDER?

There are 4 magical ways to walk through a tree:

1️⃣ Inorder (Left → Root → Right)

Visit left family first, then yourself, then right family.

     4
    / \
   2   6
  / \
 1   3

Inorder: 1 → 2 → 3 → 4 → 6

Like reading a book: left to right!

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);    // Go left
    print(node.val);       // Visit me
    inorder(node.right);   // Go right
}

2️⃣ Preorder (Root → Left → Right)

Visit yourself FIRST, then explore left, then right.

Preorder: 4 → 2 → 1 → 3 → 6

Like introducing yourself before your family!

void preorder(TreeNode node) {
    if (node == null) return;
    print(node.val);        // Visit me first!
    preorder(node.left);    // Then left
    preorder(node.right);   // Then right
}

3️⃣ Postorder (Left → Right → Root)

Visit children FIRST, then yourself last.

Postorder: 1 → 3 → 2 → 6 → 4

Like cleaning up after your kids are done playing!

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);   // Left first
    postorder(node.right);  // Then right
    print(node.val);        // Me last!
}

4️⃣ Level Order (Floor by Floor)

Visit everyone on floor 1, then floor 2, then floor 3…

Level Order: 4 → 2, 6 → 1, 3

Like going down an elevator, meeting everyone on each floor!

void levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        print(node.val);
        if (node.left != null)
            q.add(node.left);
        if (node.right != null)
            q.add(node.right);
    }
}

📏 Tree Height and Depth

How TALL is Your Family Tree?

        👴  ← Depth 0
       /  \
      👨   👩  ← Depth 1
     /
    🧒  ← Depth 2

Depth = How many steps DOWN from the root to reach a node.

• 👴’s depth = 0 (he’s at the top!)
• 🧒’s depth = 2 (two steps down)

Height = How many steps DOWN to the FARTHEST leaf.

• 👴’s height = 2 (longest path: 👴 → 👨 → 🧒)
• 👩’s height = 0 (she’s a leaf, nowhere to go!)

The Magic Formula

int height(TreeNode node) {
    if (node == null)
        return -1;  // Empty tree has height -1

    int leftH = height(node.left);
    int rightH = height(node.right);

    return 1 + Math.max(leftH, rightH);
}

Example:

     1
    / \
   2   3
  /
 4

height(1) = 1 + max(height(2), height(3))
         = 1 + max(1, 0)
         = 2

📐 Tree Diameter

The Longest Path in Your Tree!

Diameter = The LONGEST path between ANY two nodes.

Think of stretching a rope through your tree - what’s the longest rope you can fit?

        1
       / \
      2   3
     / \
    4   5

Diameter = 4 (path: 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3)

The Trick

The longest path either:

1. Goes through the root, OR
2. Lives entirely in a subtree

int diameter = 0;  // Global variable

int height(TreeNode node) {
    if (node == null) return -1;

    int leftH = height(node.left);
    int rightH = height(node.right);

    // Update diameter (path through this node)
    diameter = Math.max(diameter,
                        leftH + rightH + 2);

    return 1 + Math.max(leftH, rightH);
}

The diameter is the longest “handshake distance” between any two family members!

💰 Binary Tree Maximum Path Sum

Finding the Richest Path!

Imagine each node has gold coins (can be negative = debt!). Find the path with the MOST gold.

       -10
       /  \
      9    20
          /  \
         15   7

Max Path Sum = 42 (path: 15 → 20 → 7)

The Strategy

At each node, you can:

• Take just the node
• Take node + left path
• Take node + right path
• Take left + node + right (if this is the “top” of your path)

int maxSum = Integer.MIN_VALUE;

int maxPathDown(TreeNode node) {
    if (node == null) return 0;

    // Get max from left (0 if negative)
    int left = Math.max(0,
                        maxPathDown(node.left));
    int right = Math.max(0,
                         maxPathDown(node.right));

    // Path through this node
    maxSum = Math.max(maxSum,
                      left + node.val + right);

    // Return max path going down
    return node.val + Math.max(left, right);
}

👨‍👩‍👧 Lowest Common Ancestor (LCA)

Finding the Shared Grandparent!

Given two family members, who is their CLOSEST shared ancestor?

        3
       / \
      5   1
     / \
    6   2

LCA(6, 2) = 5 (5 is the first common ancestor) LCA(5, 1) = 3 (they share grandpa 3)

The Logic

Starting from root, go down:

• If BOTH nodes are on the LEFT → go left
• If BOTH nodes are on the RIGHT → go right
• If they SPLIT → you found the LCA!

TreeNode LCA(TreeNode root,
             TreeNode p, TreeNode q) {
    if (root == null) return null;

    // Found one of them!
    if (root == p || root == q)
        return root;

    TreeNode left = LCA(root.left, p, q);
    TreeNode right = LCA(root.right, p, q);

    // Both sides found something = split here
    if (left != null && right != null)
        return root;

    // Otherwise, return whichever found it
    return left != null ? left : right;
}

LCA is like finding the meeting point where two branches of the family first connect!

🎯 Path Sum Problems

Does a Path Add Up to the Target?

Problem: Is there a root-to-leaf path where values sum to a target?

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

Has path sum = 22? YES! (5 → 4 → 11 → 2 = 22)

Simple Check

boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;

    // Reached a leaf - check if sum matches
    if (root.left == null &&
        root.right == null) {
        return sum == root.val;
    }

    // Try both children with remaining sum
    int remaining = sum - root.val;
    return hasPathSum(root.left, remaining)
        || hasPathSum(root.right, remaining);
}

Finding ALL Paths

void findPaths(TreeNode node, int sum,
               List<Integer> path,
               List<List<Integer>> result) {
    if (node == null) return;

    path.add(node.val);

    // Leaf node with correct sum
    if (node.left == null &&
        node.right == null &&
        sum == node.val) {
        result.add(new ArrayList<>(path));
    }

    // Continue searching
    findPaths(node.left,
              sum - node.val, path, result);
    findPaths(node.right,
              sum - node.val, path, result);

    path.remove(path.size() - 1);  // Backtrack
}

🗺️ Visual Summary

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

    B --> B1["Node, Root, Leaf"]
    C --> C1["In/Pre/Post/Level"]
    D --> D1["Height = edges to leaf"]
    E --> E1["Longest path anywhere"]
    F --> F1["Max value path"]
    G --> G1["Shared ancestor"]
    H --> H1["Target sum paths"]

🚀 Quick Reference Table

🎬 The Story Ends…

You’ve just explored the magical world of Binary Trees! 🌲

Remember:

• Trees grow upside down (root at top!)
• Each parent has max 2 kids (binary = two)
• Traversals are just different ways to visit everyone
• Height is how tall, Depth is how deep
• Diameter is the longest rope through the tree
• LCA finds where family branches meet

Now go climb some trees! 🧗‍♂️