Skip to content

Monotonic Stack on Trees

Monotonic stack tracks the rightmost path during BST construction

The Same Tool, Different Shape

In array problems, a monotonic stack processes elements left-to-right, maintaining a sorted invariant. The stack answers questions like "what's the next greater element?" in \(O(n)\).

On trees, the same idea works. The difference: instead of processing a flat sequence, you're processing a traversal sequence. The stack maintains a structural invariant related to the tree — typically the rightmost path from root to the current insertion point.

The Problem: Build a BST from Preorder

LC 1008. Given the preorder traversal of a BST, reconstruct the tree.

Input: [8, 5, 1, 7, 10, 12]

Expected BST:

        8
       / \
      5   10
     / \    \
    1   7    12

The brute force: For each element, walk down the tree to find where it belongs. That's \(O(n \cdot h)\), which is \(O(n^2)\) for a skewed tree.

The monotonic stack approach: \(O(n)\).

Why Preorder + BST = Monotonic Stack

In preorder, you visit the root first, then the left subtree, then the right subtree. In a BST, left children are smaller and right children are larger.

So in the preorder sequence [8, 5, 1, 7, 10, 12]: - 8 is the root - 5 < 8, so 5 is in the left subtree of 8 - 1 < 5, so 1 is in the left subtree of 5 - 7 > 1 and 7 > 5? No, 7 > 1 but 7 < 8. So 7 is the right child of 5. - 10 > 8, so 10 is in the right subtree of 8 - 12 > 10, so 12 is in the right subtree of 10

The key observation: at any point, the stack holds the rightmost path of the tree built so far (from root down to the most recently added node). When a new value arrives:

  • If it's smaller than the stack top: it's the left child of the top.
  • If it's larger than the stack top: pop nodes until you find a node larger than the new value (or the stack empties). The last popped node becomes the parent — the new value is its right child.

This is a monotonic stack. The stack maintains a decreasing sequence (from bottom to top) at all times — which is exactly the rightmost path of a BST during construction.

Full Trace

Input: [8, 5, 1, 7, 10, 12]

Step Value Stack (bottom→top) Action Tree edge created
1 8 [8] Create root —
2 5 [8, 5] 5 < 8 → left child of 8 8.left = 5
3 1 [8, 5, 1] 1 < 5 → left child of 5 5.left = 1
4 7 Pop 1 (7>1), pop 5 (7>5). Stop at 8 (7<8). Last popped = 5. Push 7. → [8, 7] right child of 5 5.right = 7
5 10 Pop 7 (10>7), pop 8 (10>8). Stack empty. Last popped = 8. Push 10. → [10] right child of 8 8.right = 10
6 12 Pop 10 (12>10). Stack empty. Last popped = 10. Push 12. → [12] right child of 10 10.right = 12

Result tree:

        8
       / \
      5   10
     / \    \
    1   7    12

Verify via inorder: 1, 5, 7, 8, 10, 12. Sorted. Correct BST.

Why the Stack IS the Rightmost Path

After step 3, the stack is [8, 5, 1]. The tree so far:

    8
   /
  5
 /
1

The rightmost path from root: 8 → 5 → 1. That's exactly the stack, bottom to top.

After step 4 (inserting 7), we pop 1 and 5 (both < 7), making 7 the right child of 5. Stack becomes [8, 7]:

    8
   /
  5
 / \
1   7

Rightmost path: 8 → 5 → 7? No — the rightmost path from root is 8, and then... 8's right child doesn't exist yet. The stack [8, 7] represents the candidates for being the parent of the next node: 8 and 7, where 7 is the deepest rightmost node.

The stack always holds the nodes on the path from root to the current rightmost leaf, pruned to only include nodes that could still receive a right child.

The monotonic stack on a tree tracks the rightmost path. Popping = "this node's right subtree is complete." Pushing = "extending the rightmost path deeper."

The Code

TreeNode* bstFromPreorder(vector<int>& preorder) {
    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> rightmostPath;
    rightmostPath.push(root);

    for (int i = 1; i < (int)preorder.size(); i++) {
        TreeNode* newNode = new TreeNode(preorder[i]);

        if (preorder[i] < rightmostPath.top()->val) {
            rightmostPath.top()->left = newNode;
        } else {
            TreeNode* lastPopped = nullptr;
            while (!rightmostPath.empty() && preorder[i] > rightmostPath.top()->val) {
                lastPopped = rightmostPath.top();
                rightmostPath.pop();
            }
            lastPopped->right = newNode;
        }

        rightmostPath.push(newNode);
    }

    return root;
}

Complexity: \(O(n)\) time (each node is pushed and popped at most once), \(O(n)\) space.

Connection to Array Monotonic Stacks

In the "next greater element" array problem, you maintain a decreasing stack. When a new element is larger, you pop — and each popped element's "next greater" is the new element.

Here, the same thing happens structurally. When a new BST value is larger than the stack top, you pop — and each popped node's subtree is "completed" (no more right children will be added to it).

Array Mono-Stack Tree Mono-Stack
Stack = unsolved elements waiting for a greater value Stack = rightmost path nodes waiting for a right child
Pop = this element found its next greater Pop = this node's right subtree is now finalized
Push = new element enters the "waiting" pool Push = extending the rightmost path

The mental model transfers directly. If you understand monotonic stacks on arrays, you understand them on trees — the underlying mechanism is identical.

Try It

Input: [8, 5, 1, 7, 10, 12]
Output (inorder): 1 5 7 8 10 12

Predict before running: What if the preorder is sorted in decreasing order, like [5, 4, 3, 2, 1]? Every value is smaller than the top, so it always becomes a left child. You get a left-skewed tree. The stack grows to size \(n\). No pops until... actually no pops at all.

Challenge: What if the preorder is sorted in increasing order, like [1, 2, 3, 4, 5]? Each value pops everything, then pushes. You get a right-skewed tree.

Challenge 2: Can you construct a BST from postorder traversal using a similar approach? Think about processing the postorder array from right to left.

Edge Cases to Watch For

  • Sorted ascending input (e.g., [1, 2, 3, 4, 5]): every new value pops the entire stack, producing a right-skewed BST. The last popped node becomes the new node's left child — if your code doesn't track the last popped node, the left subtree is lost.
  • Sorted descending input (e.g., [5, 4, 3, 2, 1]): every new value is smaller than the top, so it always becomes a left child with zero pops. Tests that the "no pop" path correctly attaches the node.
  • Duplicate values: Not valid for a BST preorder (BST keys are unique), but if encountered, the > vs. >= comparison must be consistent with the BST definition used. Getting this wrong places nodes on the wrong side.

Problems

Problem Link Difficulty
LC 1008 — Construct BST from Preorder Traversal leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal Medium
LC 654 — Maximum Binary Tree leetcode.com/problems/maximum-binary-tree Medium
LC 739 — Daily Temperatures leetcode.com/problems/daily-temperatures Medium