Tree Operations

🌳 Binary Tree Magic: Tree Operations

Imagine you have a family tree made of LEGO blocks. Today, we’ll learn how to flip it upside down, check if two trees are twins, hide one tree inside another, build trees from clues, save trees to send to friends, and flatten trees into a single line!

🪞 Invert Binary Tree (The Mirror Trick)

What Does “Invert” Mean?

Think of looking in a mirror. Your left hand appears on the right side, and your right hand appears on the left. That’s exactly what inverting a binary tree does!

   Before:          After:
      4               4
     / \             / \
    2   7    →      7   2
   / \ / \         / \ / \
  1  3 6  9       9  6 3  1

The Secret Recipe

At every node, just swap the left and right children!

TreeNode invert(TreeNode root) {
    if (root == null) return null;

    // Swap left and right
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    // Do the same for children
    invert(root.left);
    invert(root.right);

    return root;
}

Why Is This Famous?

This is one of the most famous coding interview questions. The lesson? Simple problems can stump even experienced programmers!

👯 Same Tree and Symmetric Tree

Same Tree: Are These Twins?

Two trees are the “same” if they have identical structure AND identical values.

  Tree A:     Tree B:     Same? ✓
     1           1
    / \         / \
   2   3       2   3

boolean isSameTree(TreeNode p, TreeNode q) {
    // Both empty? Same!
    if (p == null && q == null) return true;

    // One empty, one not? Different!
    if (p == null || q == null) return false;

    // Different values? Different!
    if (p.val != q.val) return false;

    // Check both sides
    return isSameTree(p.left, q.left) &&
           isSameTree(p.right, q.right);
}

Symmetric Tree: Is This a Butterfly?

A tree is symmetric if it’s a mirror of itself. Like a butterfly - the left wing mirrors the right wing!

    Symmetric:        Not Symmetric:
        1                   1
       / \                 / \
      2   2               2   2
     / \ / \               \   \
    3  4 4  3               3   3

boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;

    return (a.val == b.val) &&
           isMirror(a.left, b.right) &&
           isMirror(a.right, b.left);
}

The trick: For symmetry, compare left’s left with right’s right, and left’s right with right’s left!

🎁 Subtree of Another Tree

What’s a Subtree?

A subtree is a tree hidden inside another tree. Like finding a small LEGO castle inside a bigger LEGO kingdom!

  Main Tree:         Subtree:
       3                4
      / \              / \
     4   5            1   2
    / \
   1   2

Is subtree of main tree? ✓ YES!

The Detective Method

1. Search the main tree for a node matching the subtree’s root
2. When found, check if that whole section matches

boolean isSubtree(TreeNode root, TreeNode sub) {
    if (root == null) return false;

    // Found a match? Check if trees are same
    if (isSameTree(root, sub)) return true;

    // Keep searching left and right
    return isSubtree(root.left, sub) ||
           isSubtree(root.right, sub);
}

🏗️ Binary Tree Construction from Traversals

The Mystery: Building a Tree from Clues

Imagine you have puzzle pieces. Traversals give you clues about how the tree was explored. With the right clues, you can rebuild the original tree!

The Three Traversals

The Magic Combination

Preorder + Inorder = Complete Tree! Postorder + Inorder = Complete Tree!

Preorder: [3, 9, 20, 15, 7]
Inorder:  [9, 3, 15, 20, 7]

Step 1: Preorder[0] = 3 is the root
Step 2: Find 3 in Inorder → index 1
Step 3: Left subtree has [9], Right has [15,20,7]

Result:
      3
     / \
    9   20
       /  \
      15   7

TreeNode build(int[] pre, int[] in) {
    return build(pre, 0, pre.length-1,
                 in, 0, in.length-1);
}

TreeNode build(int[] pre, int ps, int pe,
               int[] in, int is, int ie) {
    if (ps > pe) return null;

    TreeNode root = new TreeNode(pre[ps]);
    int rootIdx = findIndex(in, pre[ps]);
    int leftSize = rootIdx - is;

    root.left = build(pre, ps+1, ps+leftSize,
                      in, is, rootIdx-1);
    root.right = build(pre, ps+leftSize+1, pe,
                       in, rootIdx+1, ie);
    return root;
}

📦 Serialization and Deserialization

What Is Serialization?

Turning a tree into a string you can save or send! Like taking a photo of your LEGO creation so you can rebuild it later.

       1
      / \
     2   3         →   "1,2,null,null,3,4,5"
        / \
       4   5

Why Do We Need This?

• Save a tree to a file
• Send a tree over the internet
• Store a tree in a database

The BFS Approach

// Serialize: Tree → String
String serialize(TreeNode root) {
    if (root == null) return "";

    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            sb.append("null,");
        } else {
            sb.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        }
    }
    return sb.toString();
}

// Deserialize: String → Tree
TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;

    String[] vals = data.split(",");
    TreeNode root = new TreeNode(
        Integer.parseInt(vals[0]));
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    int i = 1;
    while (!queue.isEmpty() && i < vals.length) {
        TreeNode node = queue.poll();

        if (!vals[i].equals("null")) {
            node.left = new TreeNode(
                Integer.parseInt(vals[i]));
            queue.add(node.left);
        }
        i++;

        if (i < vals.length &&
            !vals[i].equals("null")) {
            node.right = new TreeNode(
                Integer.parseInt(vals[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

📋 Flatten Binary Tree to Linked List

The Goal

Turn a tree into a single line (linked list) using preorder traversal!

       1
      / \
     2   5
    / \   \
   3   4   6

Becomes:

1 → 2 → 3 → 4 → 5 → 6
(all nodes connected via right pointer)

The Clever In-Place Method

We process right-to-left, keeping track of the previous node:

TreeNode prev = null;

void flatten(TreeNode root) {
    if (root == null) return;

    // Process right first, then left
    flatten(root.right);
    flatten(root.left);

    // Connect current to previous
    root.right = prev;
    root.left = null;

    // Update previous
    prev = root;
}

Step-by-Step Visual

Start: Process 6 → prev = 6
       Process 5 → 5.right = 6, prev = 5
       Process 4 → prev = 4
       Process 3 → 3.right = 4, prev = 3
       Process 2 → 2.right = 3, prev = 2
       Process 1 → 1.right = 2, prev = 1

Result: 1→2→3→4→5→6

🎯 Summary: Your Tree Operations Toolkit

graph TD
    A["Tree Operations"] --> B["🪞 Invert"]
    A --> C["👯 Compare"]
    A --> D["🎁 Subtree"]
    A --> E["🏗️ Construct"]
    A --> F["📦 Serialize"]
    A --> G["📋 Flatten"]

    B --> B1["Swap left & right<br>at every node"]
    C --> C1["Same Tree: exact match"]
    C --> C2["Symmetric: mirror match"]
    D --> D1["Find node, then<br>compare subtrees"]
    E --> E1["Preorder + Inorder"]
    E --> E2["Postorder + Inorder"]
    F --> F1["Tree ↔ String<br>using BFS"]
    G --> G1["To linked list<br>via right pointers"]

💡 Key Insights

Remember: Most tree operations use recursion. Trust the recursion - it handles the complexity for you!

🚀 You’ve Got This!

These operations might seem tricky at first, but they all follow a pattern:

1. Handle the base case (null check)
2. Process the current node
3. Recursively handle children

Practice each operation a few times, and soon they’ll feel as natural as building with LEGO blocks! 🧱