Tree Operations

🌳 Binary Tree Operations: The Magic Mirror Garden

Imagine you have a magical garden where trees can do amazing tricks. Today, we’ll learn how these special trees can flip, compare, hide inside each other, be rebuilt from clues, be saved and loaded, and even stretch into chains!

🪞 1. Invert Binary Tree: The Magic Mirror

The Story

Imagine standing in front of a mirror. Your left hand appears on the right side, and your right hand appears on the left. Inverting a binary tree works exactly the same way!

Every node’s left child swaps places with its right child. It’s like the tree looked at itself in a mirror.

How It Works

// Before: Mirror time!
//     4
//    / \
//   2   7
//  / \ / \
// 1  3 6  9

function invertTree(root) {
  if (root === null) return null;

  // Swap left and right children
  let temp = root.left;
  root.left = root.right;
  root.right = temp;

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

  return root;
}

// After: Everything flipped!
//     4
//    / \
//   7   2
//  / \ / \
// 9  6 3  1

🎯 The Key Insight

At every node, we:

1. Swap the left and right children
2. Repeat for all children below

It’s like teaching every branch to look in the mirror!

graph TD
    A["Start at Root"] --> B["Swap left ↔ right"]
    B --> C["Go to left child"]
    B --> D["Go to right child"]
    C --> E["Repeat swap"]
    D --> F["Repeat swap"]

👯 2. Same Tree & Symmetric Tree: Twin Detectives

Same Tree: Finding Identical Twins

Two trees are the same if:

• They have the same shape
• Every matching node has the same value

Think of it like checking if two LEGO towers are built exactly the same way!

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

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

  // Values different? Not the same!
  if (p.val !== q.val) {
    return false;
  }

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

Symmetric Tree: The Butterfly Test

A tree is symmetric if its left side is a mirror image of its right side. Like a butterfly’s wings!

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

function isMirror(t1, t2) {
  // Both empty = mirror match!
  if (t1 === null && t2 === null) {
    return true;
  }

  // One empty = not mirror
  if (t1 === null || t2 === null) {
    return false;
  }

  // Check: value same AND
  // left matches other's right
  return t1.val === t2.val &&
    isMirror(t1.left, t2.right) &&
    isMirror(t1.right, t2.left);
}

🔍 Visual Example

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

Left mirrors Right!       Left doesn't mirror Right

🔍 3. Subtree of Another Tree: Finding Hidden Trees

The Story

Imagine you have a big family photo. Can you find a smaller photo hidden inside it that matches exactly? That’s what subtree checking does!

A tree subRoot is a subtree of root if somewhere in root, there’s a node that starts an exact copy of subRoot.

function isSubtree(root, subRoot) {
  // No main tree? Can't contain anything
  if (root === null) return false;

  // Does it match starting here?
  if (isSameTree(root, subRoot)) {
    return true;
  }

  // Try left and right children
  return isSubtree(root.left, subRoot) ||
         isSubtree(root.right, subRoot);
}

// Reuse our isSameTree function!
function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  return p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right);
}

🎯 Example

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

Is [4,1,2] inside [3,4,5,1,2]? YES! ✅
Starting at node 4, it matches exactly!

🧱 4. Binary Tree Construction from Traversals

The Detective Game

Imagine someone walked through a forest and wrote down trees they saw in different orders. Can you rebuild the forest from their notes?

Two types of clues:

• Preorder: Visit yourself FIRST, then left, then right
• Inorder: Visit left, then YOURSELF, then right

With both clues together, we can rebuild the tree!

The Magic Recipe

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;

  // First preorder value = ROOT
  let rootVal = preorder[0];
  let root = { val: rootVal };

  // Find root in inorder
  let rootIdx = inorder.indexOf(rootVal);

  // Everything LEFT of root in inorder
  // = left subtree
  let leftInorder = inorder.slice(0, rootIdx);
  let rightInorder = inorder.slice(rootIdx + 1);

  // Match sizes in preorder
  let leftPreorder = preorder.slice(
    1, 1 + leftInorder.length
  );
  let rightPreorder = preorder.slice(
    1 + leftInorder.length
  );

  // Build subtrees
  root.left = buildTree(leftPreorder, leftInorder);
  root.right = buildTree(rightPreorder, rightInorder);

  return root;
}

📝 Example

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

Step 1: Root = 3 (first in preorder)
Step 2: In inorder, left of 3 = [9]
                     right of 3 = [15,20,7]
Step 3: Build left subtree from [9]
Step 4: Build right subtree from [20,15,7]

Result:
    3
   / \
  9  20
    /  \
   15   7

graph TD
    A["Get first from preorder"] --> B[That's the ROOT]
    B --> C["Find root in inorder"]
    C --> D["Left side = Left subtree"]
    C --> E["Right side = Right subtree"]
    D --> F["Recurse on left"]
    E --> G["Recurse on right"]

💾 5. Serialization and Deserialization

The Story

Imagine you built an amazing LEGO castle. You need to pack it in a box and rebuild it later. How do you remember exactly how it looked?

Serialization = Taking the tree apart and writing instructions Deserialization = Reading instructions and rebuilding

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

  return root.val + "," +
         serialize(root.left) + "," +
         serialize(root.right);
}

// Example:
//     1
//    / \
//   2   3
//      / \
//     4   5
// Becomes: "1,2,null,null,3,4,null,null,5,null,null"

// DESERIALIZE: String → Tree
function deserialize(data) {
  let values = data.split(",");
  let index = 0;

  function build() {
    if (values[index] === "null") {
      index++;
      return null;
    }

    let node = { val: parseInt(values[index]) };
    index++;
    node.left = build();
    node.right = build();
    return node;
  }

  return build();
}

🎯 Key Points

• We use “null” as a marker for empty spots
• Preorder traversal keeps the structure intact
• The order of values tells us exactly how to rebuild

⛓️ 6. Flatten Binary Tree to Linked List

The Story

Imagine taking a branching river and straightening it into one long stream. Every branch becomes part of the main flow, going only to the right!

The Goal

Transform this:

    1
   / \
  2   5
 / \   \
3   4   6

Into this (linked list using right pointers):

1 → 2 → 3 → 4 → 5 → 6 → null

The Solution

function flatten(root) {
  if (root === null) return;

  // Flatten left and right subtrees first
  flatten(root.left);
  flatten(root.right);

  // Save the right subtree
  let rightSubtree = root.right;

  // Move left subtree to right
  root.right = root.left;
  root.left = null;

  // Find the end of new right
  let current = root;
  while (current.right !== null) {
    current = current.right;
  }

  // Attach original right subtree
  current.right = rightSubtree;
}

🎯 The Pattern (Preorder)

The result follows preorder traversal:

1. Process yourself
2. Then all left descendants
3. Then all right descendants

graph TD
    A["Flatten left subtree"] --> B["Flatten right subtree"]
    B --> C["Move left to right"]
    C --> D["Find end of chain"]
    D --> E["Attach original right"]

🌟 Summary: Your Tree Operation Toolkit

💡 Remember This!

Trees are just nodes with children. Every operation breaks down into:

1. Handle the current node
2. Repeat for children (recursion)

When you master this pattern, every tree problem becomes a puzzle you know how to solve! 🧩