DEV Community

Dev Cookies
Dev Cookies

Posted on

🌲 Blog 7: Tree Modification Problems in Binary Trees

🔍 Why This Pattern?

Not all tree problems are about querying or checking.
Some require changing the structure of the tree itself:

  • Inverting / mirroring
  • Flattening into a linked list
  • Converting into another data representation (array, string)
  • Pruning nodes

These are destructive transformations or constructive building problems.

🛠 Core Idea (Template)

When asked to modify a tree, the pattern is:

  1. Postorder traversal → modify children first, then parent.
  2. Rewire pointers carefully.
  3. Return the modified root to rebuild correctly.

✅ Classic Problems

1. Invert Binary Tree (LeetCode 226)

Swap left & right child at every node.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
Enter fullscreen mode Exit fullscreen mode

Pattern: Postorder swap.

2. Flatten Binary Tree to Linked List (LeetCode 114)

Transform tree into a linked list (preorder sequence).

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);

        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;

        TreeNode curr = root;
        while (curr.right != null) curr = curr.right;
        curr.right = temp;
    }
}
Enter fullscreen mode Exit fullscreen mode

Pattern: Recursive flatten + rewire.

3. Delete Node in a BST (LeetCode 450)

Remove a node and maintain BST property.

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (key < root.val) root.left = deleteNode(root.left, key);
        else if (key > root.val) root.right = deleteNode(root.right, key);
        else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            // Find inorder successor (min value in right subtree)
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }
}
Enter fullscreen mode Exit fullscreen mode

Pattern: Recursive delete + rebuild tree.

4. Trim a BST (LeetCode 669)

Keep only nodes in range [low, high].

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        if (root.val < low) return trimBST(root.right, low, high);
        if (root.val > high) return trimBST(root.left, low, high);

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
Enter fullscreen mode Exit fullscreen mode

Pattern: Conditional pruning.

5. Binary Tree Pruning (LeetCode 814)

Remove subtrees not containing 1.

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if (root.val == 0 && root.left == null && root.right == null) return null;
        return root;
    }
}
Enter fullscreen mode Exit fullscreen mode

Pattern: Postorder delete.

🚀 Advanced Variations

  1. Serialize & Deserialize Tree (LeetCode 297)
  • Encode tree into string / array.
  • Decode back into tree.
  1. Convert Sorted Array/List to BST
  • Build balanced BST from sorted input (divide & conquer).
  1. BST to Greater Sum Tree (LeetCode 1038)
  • Modify nodes so that each becomes sum of all greater values.

🎯 Quick Pattern Checklist

  • ✅ Invert / Mirror → simple postorder swap.
  • ✅ Flatten / Transform → recursive + rewire.
  • ✅ Delete / Trim / Prune → postorder remove.
  • ✅ Serialize / Deserialize → encode + decode recursively.
  • ✅ Build / Convert → recursion with divide & conquer.

🔥 Key Takeaway:
Tree modification problems are about rewiring pointers with recursion.
Think in terms of postorder traversal, because children must be processed before modifying the parent.

Top comments (0)