7. Trees

One place to revise everything about Trees before your upcoming interview.

1️⃣ What is a Tree?

A Tree is a non-linear, hierarchical data structure where a single node (the root) connects to zero or more child nodes, forming a recursive structure.

graph TD
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))
    3 --> 6((6))
    3 --> 7((7))

    classDef default fill:#1e1e2e,stroke:#cba6f7,stroke-width:2px,color:#cdd6f4;
    classDef root fill:#f38ba8,stroke:#e64553,stroke-width:2px,color:#11111b;
    class 1 root;

Key Terminology

Term	Definition
Node	An element that holds data
Root	The topmost node (no parent)
Parent	A node directly above another
Child	A node directly below another
Siblings	Nodes sharing the same parent
Leaf	A node with no children
Depth	Number of edges from root to the node
Height	Number of edges from the node to the deepest leaf
Ancestor	Any node on the path from a node up to the root
Descendant	Any node reachable going down from a node

Types of Binary Trees

Type	Property
Full (Strict)	Every node has exactly 0 or 2 children
Complete	All levels completely filled except last, which is filled left-to-right
Perfect	All internal nodes have 2 children AND all leaves are at the same level
Balanced	Height of left and right subtrees differ by at most 1
Skewed (Degenerate)	Every node has at most 1 child — essentially a linked list
BST (Binary Search Tree)	Left subtree values < root < right subtree values

Node Structure

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2️⃣ The Two Traversal Paradigms

Every tree problem boils down to how you traverse the tree:

Paradigm	Data Structure	When to Use
DFS	Stack / Recursion	Path problems, tree properties, subtree computation
BFS	Queue	Level-by-level problems, shortest path in tree, side views

The Golden Rule

DFS = go deep first (recursive or with explicit stack).

BFS = go wide first (always with a queue, level by level).

If the problem says “level” or “layer” → think BFS.

If the problem says “path” or “subtree” → think DFS.

3️⃣ DFS Traversals — Recursive

NOTE

All recursive traversals: Time $O (N)$ — visit each node once.

Space $O (h)$ — recursion stack, where $h$ = height (worst case $O (N)$ for skewed tree).

Traversal Order Reference

          1
        /   \
       2     3
      / \
     4   5

Inorder   (L → Root → R):  4 2 5 1 3
Preorder  (Root → L → R):  1 2 4 5 3
Postorder (L → R → Root):  4 5 2 3 1

Memory Trick

Inorder → root in between left & right

Preorder → root comes before (pre) everything

Postorder → root comes after (post) everything

Inorder (Left → Root → Right) — LC 94

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);   // Process at root
    inorder(root->right, res);
}

Why Inorder Matters for BST

Inorder traversal of a BST gives elements in sorted ascending order.

This is the basis for BST validation, kth smallest, predecessor/successor etc.

Preorder (Root → Left → Right) — LC 144

void preorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);   // Process at root
    preorder(root->left, res);
    preorder(root->right, res);
}

Postorder (Left → Right → Root) — LC 145

void postorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    postorder(root->left, res);
    postorder(root->right, res);
    res.push_back(root->val);   // Process at root
}

When to Use Which DFS Order

Preorder — when you need to process root before children (e.g., cloning a tree, serialization)

Inorder — when you need sorted order in BST

Postorder — when you need to process children before root (e.g., computing height, deleting nodes, freeing memory)

4️⃣ DFS Traversals — Iterative

Unified Pattern

Both iterative inorder and preorder follow the same skeleton — the only difference is where you record root->val. This makes them easy to memorize together.

Iterative Inorder — LC 94

Go left as far as possible, push along the way. When you can’t go left, pop and go right.

vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> ans;
    while (true) {
        if (root) {
            st.push(root);
            root = root->left;
        } else {
            if (st.empty()) break;
            root = st.top(); st.pop();
            ans.push_back(root->val);    // Process AFTER popping (in-between)
            root = root->right;
        }
    }
    return ans;
}

Iterative Preorder — LC 144

Same skeleton — just record the value before pushing left (process root first).

vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> ans;
    while (true) {
        if (root) {
            ans.push_back(root->val);    // Process BEFORE going left (pre = root first)
            st.push(root);
            root = root->left;
        } else {
            if (st.empty()) break;
            root = st.top(); st.pop();
            root = root->right;
        }
    }
    return ans;
}

Inorder vs Preorder — Spot the Difference
INORDER:   push left → pop → RECORD → go right
PREORDER:  RECORD → push left → pop → go right
That’s it. One line moves. Everything else is identical.

Iterative Postorder (2-Stack — Easy Way) — LC 145

Trick: Modified preorder (Root → Right → Left) then reverse gives (Left → Right → Root).

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);
 
    while (!st.empty()) {
        TreeNode* curr = st.top(); st.pop();
        res.push_back(curr->val);
 
        if (curr->left)  st.push(curr->left);   // Left first (opposite of preorder)
        if (curr->right) st.push(curr->right);   // Right second
    }
    reverse(res.begin(), res.end());             // Reverse entire result
    return res;
}

Iterative Postorder (1-Stack — Optimal) — LC 145

Implementation (1-Stack Postorder)

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
 
    while (root || !st.empty()) {
        if (root) {
            st.push(root);
            root = root->left;
        } else {
            TreeNode* temp = st.top()->right;
            if (!temp) {
                temp = st.top(); st.pop();
                res.push_back(temp->val);
                while (!st.empty() && temp == st.top()->right) {
                    temp = st.top(); st.pop();
                    res.push_back(temp->val);
                }
            } else {
                root = temp;
            }
        }
    }
    return res;
}

All-in-One Traversal (Pre + In + Post in Single Pass)

Implementation & Explanation

Using a stack<pair<node*, int>> to track state:

State	Order	Action
0	Preorder	Record → push left
1	Inorder	Record → push right
2	Postorder	Record → pop

void allTraversals(TreeNode* root) {
    if (!root) return;
    stack<pair<TreeNode*, int>> st;
    st.push({root, 0});
    vector<int> pre, in, post;
 
    while (!st.empty()) {
        auto [node, state] = st.top(); st.pop();
 
        if (state == 0) {
            pre.push_back(node->val);
            st.push({node, 1});
            if (node->left) st.push({node->left, 0});
        } else if (state == 1) {
            in.push_back(node->val);
            st.push({node, 2});
            if (node->right) st.push({node->right, 0});
        } else {
            post.push_back(node->val);
        }
    }
}

// TC: O(3N) ≈ O(N) | SC: O(N)

5️⃣ Morris Traversal — O(1) Space, No Stack, No Recursion

Why Morris?

Both recursive and iterative DFS use $O (H)$ space (call stack or explicit stack).

Morris Traversal achieves $O (1)$ extra space by temporarily modifying the tree — creating threaded links from the rightmost node of the left subtree back to the current node, then restoring the tree afterward.

Morris Inorder Traversal — LC 94

Idea: For each node, find the inorder predecessor (rightmost node in left subtree). Thread its right pointer back to the current node. This lets us return to the parent without a stack.

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    while (root != NULL) {
        if (root->left == NULL) {
            ans.push_back(root->val);     // No left subtree → process & go right
            root = root->right;
        } else {
            auto leftNode = root->left;
            while (leftNode->right) leftNode = leftNode->right;   // Find predecessor
            leftNode->right = root;       // Create thread back to root
 
            auto tem = root;
            root = root->left;            // Move to left subtree
            tem->left = NULL;             // Break original left link (avoid infinite loop)
        }
    }
    return ans;
}
// TC: O(N) — each edge traversed at most 2 times | SC: O(1)

How Morris Works — Step by Step

Original:       1
              /   \
             2     3
            / \
           4   5

Step 1: root=1, left exists → find predecessor of 1 in left subtree
        Predecessor = 5 (rightmost in left subtree of 1)
        Thread: 5->right = 1, move to root->left (root=2), break 1->left

Step 2: root=2, left exists → predecessor = 4
        Thread: 4->right = 2, move to root->left (root=4), break 2->left

Step 3: root=4, no left → PRINT 4, go right (thread takes us to 2)

Step 4: root=2, no left → PRINT 2, go right (thread takes us to 5)

Step 5: root=5, no left → PRINT 5, go right (thread takes us to 1)

Step 6: root=1, no left → PRINT 1, go right (root=3)

Step 7: root=3, no left → PRINT 3, go right (NULL) → done

Output: 4 2 5 1 3 ✓ (correct inorder)

5️⃣ BFS / Level Order Traversal

Basic Level Order — LC 102

vector<int> levelOrder(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> q;
    q.push(root);
    vector<int> ans;
 
    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        ans.push_back(curr->val);
        if (curr->left)  q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
    return ans;
}

Level-by-Level (The Template You’ll Use 90% of the Time) — LC 102 🔥

vector<vector<int>> levelOrder(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> q;
    q.push(root);
    vector<vector<int>> ans;
    while(!q.empty())
    {
        vector<int> level;
        int sz = q.size();
        while(sz--) {
            auto curr = q.front(); q.pop();
            level.push_back(curr->val);
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
        } 
        ans.push_back(level);
    }
    return ans;
}
// TC: O(N) | SC: O(N) — queue holds at most one level width

The Level-by-Level BFS Template

If you want to process nodes level by level

This single template solves: zigzag, right side view, left side view, max width, average per level, etc.

Zigzag Level Order — LC 103

Same template — just reverse alternate levels:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> q;
    q.push(root);
    vector<vector<int>> ans;
    bool leftToRight = true;
 
    while (!q.empty()) {
        vector<int> level;
        int sz = q.size();
 
        while (sz--) {
            auto curr = q.front(); q.pop();
            level.push_back(curr->val);
            if (curr->left)  q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        if (!leftToRight) reverse(level.begin(), level.end());
        ans.push_back(level);
        leftToRight = !leftToRight;
    }
    return ans;
}

6️⃣ Tree Properties — The Foundation Problems

Maximum Depth — LC 104

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

Minimum Depth — LC 111

Gotcha

If one child is null, you must go to the other child, not return 0.

A node with only a right child is NOT a leaf — the minimum depth goes through the right subtree.

int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left)  return 1 + minDepth(root->right);
    if (!root->right) return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

Diameter of Binary Tree — LC 543

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The diameter passes through a node = leftHeight + rightHeight. Track global max.

int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    height(root, diameter);
    return diameter;
}
 
int height(TreeNode* root, int& diameter) {
    if (!root) return 0;
    int lh = height(root->left, diameter);
    int rh = height(root->right, diameter);
    diameter = max(diameter, lh + rh);    // Update diameter at this node
    return 1 + max(lh, rh);              // Return height
}

Balanced Binary Tree — LC 110 O(N)

Use −1 as sentinel for unbalanced. Avoid recomputing heights.

int height(TreeNode* root) {
    if(!root) return 0;
    int lh = height(root->left);
    int rh = height(root->right);
    if(lh == -1 or rh == -1) return -1;
    if(abs(lh-rh) > 1) return -1;
    return 1 + max(lh, rh); 
}
 
bool isBalanced(TreeNode* root) {
    return height(root) == -1 ? false : true;
}

Same Tree — LC 100

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if ((!p and q) or (!q and p)) return false;
    return p->val == q->val
        && isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

Symmetric Tree — LC 101

Mirror comparison — compare left.left ↔ right.right and left.right ↔ right.left:

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}
 
bool isMirror(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if ((!p and q) or (!q and p)) return false;
    return p->val == q->val
        && isMirror(p->left, q->right)
        && isMirror(p->right, q->left);
}

Invert Binary Tree — LC 226

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

7️⃣ Side Views of a Binary Tree

Right Side View — LC 199

BFS approach — last node of each level:

vector<int> rightSideView(TreeNode* root) {
    if(!root) return {};
    queue<TreeNode*> q;
    q.push(root);
    vector<int> ans;
 
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            auto curr = q.front(); q.pop();
            if (sz == 0) ans.push_back(curr->val);  // Last of level
            if (curr->left)  q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
    }
    return ans;
}

DFS approach — visit right child first, add first node at each depth:

vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    dfs(root, res, 0);
    return res;
}
 
void dfs(TreeNode* root, vector<int>& res, int level) {
    if (!root) return;
    if (res.size() == level)          // First node at this depth
        res.push_back(root->val);
    dfs(root->right, res, level + 1); // Right first for right view
    dfs(root->left, res, level + 1);
}

Left Side View — LC 513

Same DFS pattern — just visit left child first:

void dfs(TreeNode* root, vector<int>& res, int level) {
    if (!root) return;
    if (res.size() == level)
        res.push_back(root->val);
    dfs(root->left, res, level + 1);  // Left first for left view
    dfs(root->right, res, level + 1);
}

Top View & Bottom View

Use Horizontal Distance (HD): root = 0, left child = HD−1, right child = HD+1.

Top View — BFS, keep first node at each HD:

vector<int> topView(TreeNode* root) {
    if (!root) return {};
    map<int, int> hdMap;                         // HD → node value (ordered map)
    queue<pair<TreeNode*, int>> q;               // node, hd
    q.push({root, 0});
 
    while (!q.empty()) {
        auto [node, hd] = q.front(); q.pop();
        if (!hdMap.count(hd))        // First node at this HD wins
            hdMap[hd] = node->val;
        if (node->left)  q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
 
    vector<int> res;
    for (auto& [hd, val] : hdMap) res.push_back(val);
    return res;
}

Bottom View — same BFS, but overwrite at each HD (last node wins):

// Only difference from Top View: remove the if-check, always overwrite
hdMap[hd] = node->val;  // Every node overwrites → last (deepest) wins

Top View vs Bottom View

Top View → if (!map.count(hd)) — first node at each HD (BFS ensures shallowest first)

Bottom View → always overwrite — last node at each HD (BFS ensures deepest last)

Both use map<int, int> (ordered by HD) to get left-to-right order.

Boundary Traversal (Anti-clockwise) — LC 545

Three parts: Left boundary (top-down, exclude leaf) → All leaves (left-to-right) → Right boundary (bottom-up, exclude leaf).

bool isLeaf(TreeNode* root) {
    return !root->left && !root->right;
}
 
void leftBoundary(TreeNode* root, vector<int>& ans) {
    root = root->left;
    while (root) {
        if (!isLeaf(root))
            ans.push_back(root->val);
        if (root->left)
            root = root->left;
        else
            root = root->right;
    }
}
 
void leaves(TreeNode* root, vector<int>& ans) {
    if (!root) return;
    if (isLeaf(root)) ans.push_back(root->val);
    leaves(root->left, ans);
    leaves(root->right, ans);
}
 
void rightBoundary(TreeNode* root, vector<int>& ans) {
    root = root->right;
    vector<int> r;
    while (root) {
        if (!isLeaf(root))
            r.push_back(root->val);
        if (root->right)
            root = root->right;
        else
            root = root->left;
    }
    reverse(r.begin(), r.end());
    for (auto &i : r) ans.push_back(i);
}
 
vector<int> boundaryTraversal(TreeNode* root) {
    if (!root) return {};
    if (isLeaf(root)) return {root->val};
 
    vector<int> ans;
    ans.push_back(root->val);
    leftBoundary(root, ans);
    leaves(root, ans);
    rightBoundary(root, ans);
    return ans;
}

8️⃣ Path Problems

Path Sum (Root to Leaf) — LC 112

bool hasPathSum(TreeNode* root, int target) {
	if (!root) return false;
	t -= root->val;
	if (!root->left && !root->right && t == 0) return true; // Leaf check
 
	return hasPathSum(root->left, t) || hasPathSum(root->right, t);
}

Path Sum III — LC 437 🔥

int pathSum(TreeNode* root, int targetSum) {
    unordered_map<long long, int> prefixMap;
    prefixMap[0] = 1;  // Empty prefix
    return dfs(root, 0, targetSum, prefixMap);
}
 
int dfs(TreeNode* root, long long currSum, int target,
        unordered_map<long long, int>& prefixMap) {
    if (!root) return 0;
 
    currSum += root->val;
    int count = prefixMap[currSum - target];   // Paths ending here
 
    prefixMap[currSum]++;                       // Add current prefix
    count += dfs(root->left, currSum, target, prefixMap);
    count += dfs(root->right, currSum, target, prefixMap);
    prefixMap[currSum]--;                       // Backtrack
 
    return count;
}
// TC: O(N) | SC: O(N)

Path Sum III Pattern

This is the prefix sum + hashmap technique adapted for trees.

currSum - target existing in the prefix map means there’s a sub-path summing to target.

Backtrack the prefix map when returning from a subtree — crucial for correctness.

Binary Tree Maximum Path Sum — LC 124 🔥

Any node to any node (not necessarily root-to-leaf). Classic interview problem.

int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    maxGain(root, maxSum);
    return maxSum;
}
 
int maxGain(TreeNode* root, int& maxSum) {
    if (!root) return 0;
    int left  = max(0, maxGain(root->left, maxSum));   // Ignore negative paths
    int right = max(0, maxGain(root->right, maxSum));
 
    maxSum = max(maxSum, left + root->val + right);    // Path through this node
    return root->val + max(left, right);               // Return best single branch
}

Key Insight

At each node, the path through it = leftGain + val + rightGain (this updates global max).

But we can only return one branch upward (left OR right, not both) — a path can’t fork.

9️⃣ Lowest Common Ancestor (LCA)

LCA of Binary Tree — LC 236 🔥

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
 
    TreeNode* left  = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
 
    if (left && right) return root;   // p and q are in different subtrees
    return left ? left : right;       // Both in same subtree
}
// TC: O(N) | SC: O(H)

LCA Intuition

If p is found in the left subtree and q in the right subtree → current root is the LCA.

If both found on one side → the LCA is deeper on that side (returned by recursive call).

LCA of BST — LC 235 O(H)

Use BST property to avoid searching unnecessary subtrees:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (p->val < root->val && q->val < root->val)
        return lowestCommonAncestor(root->left, p, q);
    if (p->val > root->val && q->val > root->val)
        return lowestCommonAncestor(root->right, p, q);
    return root;  // Split point — this is the LCA
}

🔟 BST-Specific Patterns

Validate BST — LC 98

Pass (min, max) range down. Every node must be within its valid range.

bool isValidBST(TreeNode* root) {
    return validate(root, LONG_MIN, LONG_MAX);
}
 
bool validate(TreeNode* root, long minVal, long maxVal) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return validate(root->left, minVal, root->val)
        && validate(root->right, root->val, maxVal);
}

Kth Smallest Element in BST — LC 230

Inorder traversal gives sorted order. Just count to k.

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) { st.push(root); root = root->left; }
        root = st.top(); st.pop();
        if (--k == 0) return root->val;
        root = root->right;
    }
    return -1;  // Should not reach here
}
// TC: O(H + k) | SC: O(H)

Delete Node in BST — LC 450

Three cases:

Leaf → remove
One child → replace with child
Two children → replace with inorder successor (smallest in right subtree)

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    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) return root->right;
        if (!root->right) return root->left;
        // Two children: find inorder successor
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

Insert into BST — LC 701

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}

Recover BST — LC 99

During inorder, if prev->val > curr->val, we found a violation.

First violation → first = prev, second = curr
Second violation → update second = curr

TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
 
void recoverTree(TreeNode* root) {
    inorder(root);
    swap(first->val, second->val);
}
 
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    if (prev && prev->val > root->val) {
        if (!first) first = prev;
        second = root;
    }
    prev = root;
    inorder(root->right);
}

1️⃣1️⃣ Tree Construction

From Preorder & Inorder — LC 105 🔥

Preorder: [3, 9, 20, 15, 7]    Inorder: [9, 3, 15, 20, 7]
           ↑ root                        ← left | right →

preorder[0] = 3 = root
In inorder: everything left of 3 = left subtree, right of 3 = right subtree

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inMap;
    for (int i = 0; i < inorder.size(); i++)
        inMap[inorder[i]] = i;
 
    int preIdx = 0;
    return build(preorder, preIdx, 0, inorder.size() - 1, inMap);
}
 
TreeNode* build(vector<int>& preorder, int& preIdx, int inLeft, int inRight,
                unordered_map<int, int>& inMap) {
    if (inLeft > inRight) return nullptr;
 
    TreeNode* root = new TreeNode(preorder[preIdx++]);
    int inIdx = inMap[root->val];
 
    root->left  = build(preorder, preIdx, inLeft, inIdx - 1, inMap);
    root->right = build(preorder, preIdx, inIdx + 1, inRight, inMap);
    return root;
}
// TC: O(N) | SC: O(N) for hashmap

From Inorder & Postorder — LC 106

Same idea: postorder[last] = root. Build right subtree first (postorder goes right-to-left).

TreeNode* build(vector<int>& postorder, int& postIdx, int inLeft, int inRight,
                unordered_map<int, int>& inMap) {
    if (inLeft > inRight) return nullptr;
 
    TreeNode* root = new TreeNode(postorder[postIdx--]);
    int inIdx = inMap[root->val];
 
    root->right = build(postorder, postIdx, inIdx + 1, inRight, inMap);  // Right first!
    root->left  = build(postorder, postIdx, inLeft, inIdx - 1, inMap);
    return root;
}

Sorted Array to BST — LC 108

Pick the middle element as root → guarantees balanced tree.

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, nums.size() - 1);
}
 
TreeNode* build(vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left  = build(nums, left, mid - 1);
    root->right = build(nums, mid + 1, right);
    return root;
}

BST from Preorder — LC 1008

Use upper bound approach — O(N):

TreeNode* bstFromPreorder(vector<int>& preorder) {
    int idx = 0;
    return build(preorder, idx, INT_MAX);
}
 
TreeNode* build(vector<int>& preorder, int& idx, int bound) {
    if (idx == preorder.size() || preorder[idx] > bound) return nullptr;
    TreeNode* root = new TreeNode(preorder[idx++]);
    root->left  = build(preorder, idx, root->val);
    root->right = build(preorder, idx, bound);
    return root;
}

1️⃣2️⃣ Serialize & Deserialize

Binary Tree — LC 297 💀

Use preorder with null markers ("#"):

// Serialize: preorder with null markers
string serialize(TreeNode* root) {
    if (!root) return "#";
    return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}
 
// Deserialize: read tokens from queue
TreeNode* deserialize(string data) {
    queue<string> tokens;
    stringstream ss(data);
    string token;
    while (getline(ss, token, ',')) tokens.push(token);
    return buildTree(tokens);
}
 
TreeNode* buildTree(queue<string>& tokens) {
    string val = tokens.front(); tokens.pop();
    if (val == "#") return nullptr;
    TreeNode* node = new TreeNode(stoi(val));
    node->left  = buildTree(tokens);
    node->right = buildTree(tokens);
    return node;
}

1️⃣3️⃣ Distance & Relation Problems

All Nodes Distance K — LC 863 🔥

Build a parent map, then BFS from target node for k levels:

vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    unordered_map<TreeNode*, TreeNode*> parent;
    buildParentMap(root, nullptr, parent);
 
    queue<TreeNode*> q;
    unordered_set<TreeNode*> visited;
    q.push(target);
    visited.insert(target);
 
    while (!q.empty() && k > 0) {
        int sz = q.size();
        while (sz--) {
            auto curr = q.front(); q.pop();
            // Go left, right, AND parent
            for (auto next : {curr->left, curr->right, parent[curr]}) {
                if (next && !visited.count(next)) {
                    visited.insert(next);
                    q.push(next);
                }
            }
        }
        k--;
    }
 
    vector<int> ans;
    while (!q.empty()) { ans.push_back(q.front()->val); q.pop(); }
    return ans;
}
 
void buildParentMap(TreeNode* root, TreeNode* par,
                    unordered_map<TreeNode*, TreeNode*>& parent) {
    if (!root) return;
    parent[root] = par;
    buildParentMap(root->left, root, parent);
    buildParentMap(root->right, root, parent);
}

The Parent Map Trick

Trees only have downward pointers. To traverse upward, build a parent map first.

Then BFS works in all 3 directions: left, right, parent — like a graph.

🧠 Master Cheatsheet

The Decision Framework

What does the problem ask?
│
├── "Traverse the tree"
│   ├── Level-by-level?  → BFS with queue
│   └── Path / subtree?  → DFS (recursion or stack)
│
├── "Tree property" (depth, balanced, symmetric, same)
│   └── DFS — compute bottom-up, return value from recursion
│
├── "Side view" (left, right, top, bottom)
│   ├── Left/Right → BFS (first/last of level) or DFS (depth tracking)
│   └── Top/Bottom → BFS with Horizontal Distance + ordered map
│
├── "Path sum" / "root to leaf"
│   ├── Single path exists? → DFS with target subtraction
│   ├── All paths?          → DFS + backtracking
│   └── Any-to-any path?   → Prefix sum + hashmap on tree
│
├── "Lowest Common Ancestor"
│   ├── Binary Tree → Recursive: left/right both found = root is LCA
│   └── BST → Use BST property to pick direction
│
├── "Construct tree from traversals"
│   └── Find root from pre/postorder → split using inorder position
│
├── "BST operation" (validate, insert, delete, kth)
│   └── Use BST property: left < root < right
│       └── Inorder = sorted → kth smallest, validate, recover
│
└── "Serialize / distance / misc"
    └── Serialize: preorder + null markers
    └── Distance K: parent map + BFS

Complexity Reference

Operation	Time	Space
Any single traversal	$O (N)$	$O (H)$
Level-order BFS	$O (N)$	$O (W)$ ≤ $O (N)$
BST Search / Insert / Delete	$O (H)$	$O (H)$
Balanced BST operations	$O (lo g N)$	$O (lo g N)$
Build tree from traversals	$O (N)$	$O (N)$
Serialize / Deserialize	$O (N)$	$O (N)$

Where $H$ = height ( $lo g N$ for balanced, $N$ for skewed), $W$ = max width of tree.

Pattern Recognition Table

Signal in problem	Pattern to use
”Level order” / “by level” / “zigzag”	BFS with queue, level-by-level template
”Depth” / “height” / “balanced”	DFS, bottom-up return
”Same” / “symmetric” / “mirror”	DFS, compare two trees simultaneously
”Path sum” / “root to leaf”	DFS with target subtraction
”Maximum path sum” (any to any)	DFS, `max(0, child)` + global max
”Path sum III” (any node downward)	Prefix sum + hashmap
”Right/left side view”	BFS (first/last of level) or DFS with depth
”Top/bottom view”	BFS + horizontal distance + ordered map
”Boundary traversal”	Left boundary + leaves + right boundary
”LCA”	Recursive check left/right subtrees
”Validate BST”	DFS with (min, max) range
”Kth smallest in BST”	Iterative inorder, count to k
”Construct from preorder + inorder”	Preorder[0] = root, split by inorder index
”Serialize / deserialize”	Preorder with null markers + queue
”Distance K” / “all nodes at distance”	Parent map + BFS
”Diameter”	At each node: leftH + rightH, track global

Common Gotchas

1. minDepth: if one child is null, DON'T return 0 — go to the other child
2. BST validation: use long (LONG_MIN/MAX) to handle INT_MIN/INT_MAX edge cases
3. Path Sum: check at LEAF (both children null), not just any null node
4. LCA: return root when root == p || root == q (even before checking children)
5. Postorder iterative: the 1-stack version needs careful backtracking logic
6. Tree construction: preIdx must be passed by REFERENCE (not value)
7. Side views: DFS needs level tracking; BFS needs level-by-level snapshot
8. Prefix sum on tree: MUST backtrack the map when returning from subtree
9. Max Path Sum: return one branch only (can't fork), but update global with both
10. Diameter: it's EDGES not NODES — don't add 1 to leftH + rightH

Om's Brain

Explorer

1️⃣ What is a Tree?

Key Terminology

Types of Binary Trees

Node Structure

2️⃣ The Two Traversal Paradigms

3️⃣ DFS Traversals — Recursive

Traversal Order Reference

Inorder (Left → Root → Right) — LC 94

Preorder (Root → Left → Right) — LC 144

Postorder (Left → Right → Root) — LC 145

4️⃣ DFS Traversals — Iterative

Iterative Inorder — LC 94

Iterative Preorder — LC 144

Iterative Postorder (2-Stack — Easy Way) — LC 145

Iterative Postorder (1-Stack — Optimal) — LC 145

All-in-One Traversal (Pre + In + Post in Single Pass)

5️⃣ Morris Traversal — O(1) Space, No Stack, No Recursion

Morris Inorder Traversal — LC 94

How Morris Works — Step by Step

5️⃣ BFS / Level Order Traversal

Basic Level Order — LC 102

Level-by-Level (The Template You’ll Use 90% of the Time) — LC 102 🔥

Zigzag Level Order — LC 103

6️⃣ Tree Properties — The Foundation Problems

Maximum Depth — LC 104

Minimum Depth — LC 111

Diameter of Binary Tree — LC 543

Balanced Binary Tree — LC 110 O(N)

Same Tree — LC 100

Symmetric Tree — LC 101

Invert Binary Tree — LC 226

7️⃣ Side Views of a Binary Tree

Right Side View — LC 199

Left Side View — LC 513

Top View & Bottom View

Boundary Traversal (Anti-clockwise) — LC 545

8️⃣ Path Problems

Path Sum (Root to Leaf) — LC 112

Path Sum III — LC 437 🔥

Binary Tree Maximum Path Sum — LC 124 🔥

9️⃣ Lowest Common Ancestor (LCA)

LCA of Binary Tree — LC 236 🔥

LCA of BST — LC 235 O(H)

🔟 BST-Specific Patterns

Validate BST — LC 98

Kth Smallest Element in BST — LC 230

Delete Node in BST — LC 450

Insert into BST — LC 701

Recover BST — LC 99

1️⃣1️⃣ Tree Construction

From Preorder & Inorder — LC 105 🔥

From Inorder & Postorder — LC 106

Sorted Array to BST — LC 108

BST from Preorder — LC 1008

1️⃣2️⃣ Serialize & Deserialize

Binary Tree — LC 297 💀

1️⃣3️⃣ Distance & Relation Problems

All Nodes Distance K — LC 863 🔥

🧠 Master Cheatsheet

The Decision Framework

Complexity Reference

Pattern Recognition Table

Common Gotchas

0. Questions

Table of Contents

Mindmap

Graph View