Tree Operations

🌲 Binary Tree Magic: Transforming Trees Like a Wizard!

Imagine you have a magical family tree made of toy blocks. Each block can have two children hanging below it—one on the left, one on the right. Today, we’re going to learn six amazing spells to transform, compare, build, and reshape these trees!

🪞 Spell 1: Invert Binary Tree (The Mirror Spell)

What is it?

Imagine holding your toy tree in front of a mirror. Everything flips! What was on the left now appears on the right, and vice versa. That’s exactly what “inverting” a binary tree means.

The Simple Idea

For every single block in your tree, swap its left and right children. That’s it! Do this for all blocks, and your entire tree becomes a mirror image.

graph TD
    subgraph Before
    A1["4"] --> B1["2"]
    A1 --> C1["7"]
    B1 --> D1["1"]
    B1 --> E1["3"]
    C1 --> F1["6"]
    C1 --> G1["9"]
    end

graph TD
    subgraph After Mirror
    A2["4"] --> C2["7"]
    A2 --> B2["2"]
    C2 --> G2["9"]
    C2 --> F2["6"]
    B2 --> E2["3"]
    B2 --> D2["1"]
    end

Python Code

def invertTree(root):
    if root is None:
        return None

    # Swap left and right
    root.left, root.right = (
        root.right, root.left
    )

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

    return root

Why does this work?

We visit every block (node), swap its children, then tell each child to do the same. It’s like a chain of mirror spells going down the whole tree!

👯 Spell 2: Same Tree & Symmetric Tree

Same Tree: Are Two Trees Identical Twins?

Two trees are the same if:

1. Both are empty (no blocks at all), OR
2. Both have the same value at the top, AND their left subtrees are the same, AND their right subtrees are the same.

def isSameTree(p, q):
    # Both empty? Same!
    if not p and not q:
        return True

    # One empty, one not? Different!
    if not p or not q:
        return False

    # Values different? Different!
    if p.val != q.val:
        return False

    # Check both sides
    return (isSameTree(p.left, q.left)
            and isSameTree(p.right, q.right))

Symmetric Tree: Is One Tree a Mirror of Itself?

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

graph TD
    A["1"] --> B["2"]
    A --> C["2"]
    B --> D["3"]
    B --> E["4"]
    C --> F["4"]
    C --> G["3"]

The left subtree [2,3,4] mirrors the right subtree [2,4,3].

def isSymmetric(root):
    def isMirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False

        return (t1.val == t2.val
                and isMirror(t1.left, t2.right)
                and isMirror(t1.right, t2.left))

    return isMirror(root, root)

The Secret Trick

For symmetry, we compare left’s left with right’s right, and left’s right with right’s left. It’s like checking if a butterfly’s spots match!

🔍 Spell 3: Subtree of Another Tree

What is a Subtree?

Imagine you have a big LEGO castle (Tree A). Your friend has a small LEGO tower (Tree B). Is your friend’s tower hidden somewhere inside your castle? If yes, Tree B is a subtree of Tree A!

How to Find It

1. Check if Tree B matches Tree A starting at the root
2. If not, check if Tree B is hiding in A’s left subtree
3. If not, check if Tree B is hiding in A’s right subtree

def isSubtree(root, subRoot):
    if not root:
        return False

    # Check if trees match here
    if isSameTree(root, subRoot):
        return True

    # Search in left and right
    return (isSubtree(root.left, subRoot)
            or isSubtree(root.right, subRoot))

Example

graph TD
    subgraph Big Tree
    A["3"] --> B["4"]
    A --> C["5"]
    B --> D["1"]
    B --> E["2"]
    end

graph TD
    subgraph Small Tree
    X["4"] --> Y["1"]
    X --> Z["2"]
    end

The small tree [4,1,2] is found inside the big tree!

🏗️ Spell 4: Building Trees from Traversals

The Puzzle

Imagine someone tells you: “I visited all the blocks in a tree and wrote down their values in two different orders.” Can you rebuild the original tree? Yes, you can!

The Three Ways to Walk a Tree

• Preorder: Visit parent FIRST, then left, then right → [Parent, Left..., Right...]
• Inorder: Visit left FIRST, then parent, then right → [Left..., Parent, Right...]
• Postorder: Visit left, then right, then parent LAST → [Left..., Right..., Parent]

Building from Preorder + Inorder

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None

    # First in preorder is always root
    root_val = preorder[0]
    root = TreeNode(root_val)

    # Find root in inorder
    mid = inorder.index(root_val)

    # Left of mid = left subtree
    # Right of mid = right subtree
    root.left = buildTree(
        preorder[1:mid+1],
        inorder[:mid]
    )
    root.right = buildTree(
        preorder[mid+1:],
        inorder[mid+1:]
    )

    return root

The Magic Recipe

Example

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

Step 1: 3 is root (first in preorder) Step 2: In inorder, 9 is left of 3, so [9] is left subtree Step 3: [15, 20, 7] is right subtree Step 4: Repeat for each subtree!

📦 Spell 5: Serialization & Deserialization

The Problem

How do you save a tree to a file and load it back later? Or send it over the internet? You need to convert it to text (serialize) and back to a tree (deserialize).

The Strategy

Use preorder traversal and mark empty spots with a special symbol like #.

graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["#"]
    B --> E["#"]
    C --> F["4"]
    C --> G["5"]

Serialized: "1,2,#,#,3,4,#,#,5,#,#"

Python Code

class Codec:
    def serialize(self, root):
        result = []

        def preorder(node):
            if not node:
                result.append("#")
                return
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return ",".join(result)

    def deserialize(self, data):
        values = iter(data.split(","))

        def build():
            val = next(values)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()

Why This Works

By using # for empty spots, we know exactly where each subtree ends. It’s like leaving breadcrumbs to find your way back!

📏 Spell 6: Flatten Binary Tree to Linked List

The Goal

Transform a tree into a straight line—like unfolding origami back into flat paper. The line follows preorder (root, left, right).

Before and After

graph TD
    subgraph Before
    A["1"] --> B["2"]
    A --> C["5"]
    B --> D["3"]
    B --> E["4"]
    C --> F["#"]
    C --> G["6"]
    end

After flattening:

1 → 2 → 3 → 4 → 5 → 6

All nodes link through their right pointer. Left is always None.

The Clever Trick (Morris-like)

def flatten(root):
    current = root

    while current:
        if current.left:
            # Find rightmost of left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right

            # Connect rightmost to current's right
            rightmost.right = current.right

            # Move left subtree to right
            current.right = current.left
            current.left = None

        current = current.right

Step-by-Step Example

1. Start at 1, left child is 2
2. Find rightmost of left subtree: 4
3. Connect 4.right → 5
4. Move: 1.right = 2, 1.left = None
5. Move to 2, repeat…

Result: A flat linked list using only right pointers!

🎯 Quick Summary

🌟 You’re Now a Tree Wizard!

You’ve learned six powerful spells to manipulate binary trees. Each one builds on a simple idea:

1. Think recursively—solve for one node, let children solve themselves
2. Mark what’s missing—use None or # as signals
3. Trust the pattern—the same logic works at every level

Go forth and transform trees with confidence! 🚀