Skip to content

Stack as Ancestor Tracker

DFS call stack mirrors the ancestor path from root to current node

The Observation That Connects Two Worlds

You know stacks from array problems — monotonic stacks, bracket matching, next-greater-element. You know recursion from tree problems. This chapter connects them: the call stack during DFS IS a stack of ancestors.

When you're standing at a node during recursive DFS, every function call currently on the call stack corresponds to an ancestor of the current node. The bottom of the stack is the root. The top is the current node's parent.

This isn't a metaphor. It's literally what the call stack contains. And once you see it, you can exploit it.

Problem: Nearest Greater Ancestor

For each node in a binary tree, find its nearest ancestor whose value is strictly greater. If no such ancestor exists, the answer is \(-1\).

        5
       / \
      3    8
     / \  /
    1   4 7

For node 1: ancestors are [5, 3]. Nearest greater ancestor? 3 is greater than 1, so answer is 3. For node 4: ancestors are [5, 3]. 3 is not greater than 4. 5 is greater than 4. But 3 is nearer. Wait — we need the nearest ancestor that IS greater. Walk upward: parent 3 (not greater), grandparent 5 (greater). Answer: 5. For node 7: ancestors are [5, 8]. Parent 8 is greater than 7. Answer: 8. For node 3: ancestors are [5]. 5 > 3. Answer: 5. For node 8: ancestors are [5]. 5 is not > 8. Answer: -1. For node 5: no ancestors. Answer: -1.

The Stack Approach

During DFS, maintain an explicit stack (or vector used as a stack) that holds the values of all ancestors of the current node. When you enter a node, push its value. When you leave, pop it. The stack always reflects the path from root to current node.

To find the nearest greater ancestor: scan the stack from top to bottom (parent to root) and return the first value greater than the current node.

Full Trace

DFS order: 5, 3, 1, 4, 8, 7.

Step Current node Ancestor stack (before push) Nearest greater Action
1 5 [] -1 (no ancestors) push 5
2 3 [5] 5 (top, 5 > 3) push 3
3 1 [5, 3] 3 (top, 3 > 1) push 1
— leave 1 [5, 3, 1] — pop 1
4 4 [5, 3] 5 (skip 3, check 5: 5 > 4) push 4
— leave 4 [5, 3, 4] — pop 4
— leave 3 [5, 3] — pop 3
5 8 [5] -1 (5 not > 8) push 8
6 7 [5, 8] 8 (top, 8 > 7) push 7
— leave 7 [5, 8, 7] — pop 7
— leave 8 [5, 8] — pop 8
— leave 5 [5] — pop 5

Results: node 5 → -1, node 3 → 5, node 1 → 3, node 4 → 5, node 8 → -1, node 7 → 8.

Verify node 4: ancestors of 4 are [5, 3]. Walk up: 3 is parent but 3 < 4. Next: 5 > 4. Answer: 5. Correct.

Why Push/Pop Works

The push happens when you enter a subtree. The pop happens when you leave it. This mirrors the call stack exactly:

  • dfs(5) starts → stack: [5]
  • dfs(3) starts → stack: [5, 3]
    • dfs(1) starts → stack: [5, 3, 1]
    • dfs(1) returns → stack: [5, 3]
    • dfs(4) starts → stack: [5, 3, 4]
    • dfs(4) returns → stack: [5, 3]
  • dfs(3) returns → stack: [5]
  • dfs(8) starts → stack: [5, 8]
    • ...

The explicit vector mirrors the implicit call stack. When you later move to iterative DFS (Chapter 10 Lesson 3), you'll manage this stack manually.

When you push onto the stack, you're entering a subtree. When you pop, you're leaving it. The stack contents at any moment are exactly the ancestors of the current node.

The Code

void dfs(TreeNode* root, vector<int>& ancestorStack, vector<int>& result) {
    if (!root) return;

    int nearestGreater = -1;
    for (int i = (int)ancestorStack.size() - 1; i >= 0; i--) {
        if (ancestorStack[i] > root->val) {
            nearestGreater = ancestorStack[i];
            break;
        }
    }
    result[root->val] = nearestGreater;

    ancestorStack.push_back(root->val);
    dfs(root->left, ancestorStack, result);
    dfs(root->right, ancestorStack, result);
    ancestorStack.pop_back();
}

vector<int> nearestGreaterAncestor(TreeNode* root) {
    vector<int> result(10, -1);
    vector<int> ancestorStack;
    dfs(root, ancestorStack, result);
    return result;
}

Complexity: \(O(n \cdot h)\) time in the worst case (scanning the stack at each node), \(O(h)\) space. For balanced trees, \(h = O(\log n)\).

Optimizing with a Monotonic Stack

The scan from top to bottom at each node takes \(O(h)\) worst case. Can you make it \(O(1)\)?

Yes — maintain the ancestor stack in monotonically decreasing order. Drop any ancestor that's smaller than or equal to the current node, since it can never be the "nearest greater" for any descendant.

But wait — you can't drop ancestors from the path. They're structural. You'd need a separate data structure to track the "interesting" ancestors.

This is exactly the connection to monotonic stacks from array problems, which is the topic of the next lesson.

Try It

Input: (the 6-node tree in main)
Output: Node 1: 3, Node 3: 5, Node 4: 5, Node 5: -1, Node 7: 8, Node 8: -1

Predict before running: In a BST, the nearest greater ancestor of a left child is always its parent. True or false? True for immediate left children. But for a right child of a left child, the nearest greater ancestor might be the grandparent.

Challenge: Modify the code to find the nearest smaller ancestor instead. What changes in the scan?

Challenge 2: LC 1026 — Maximum Difference Between Node and Ancestor. For each node, track the min and max values in the ancestor stack simultaneously. The answer is the maximum of (max ancestor - node value) and (node value - min ancestor) across all nodes.

Edge Cases to Watch For

  • All nodes have the same value: No ancestor is strictly greater, so every node returns \(-1\). If your comparison uses >= instead of >, you'll incorrectly report ancestors — the strict-vs-nonstrict comparison must match the problem statement.
  • Strictly increasing path from root: No node has a greater ancestor until the root; every stack scan traverses the full depth. This is the worst case for a naive linear scan of the stack — use a monotonic stack to keep amortized \(O(1)\).

Problems

Problem Link Difficulty
LC 1026 — Max Difference Between Node and Ancestor leetcode.com/problems/maximum-difference-between-node-and-ancestor Medium
LC 236 — Lowest Common Ancestor of a Binary Tree leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree Medium
LC 1123 — Lowest Common Ancestor of Deepest Leaves leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves Medium