Check if an Array Can Represent Preorder Traversal of a BST

Sandhiya Priya
3w
1.4k
0
1

Article

Problem Statement

Given an array of distinct integers, determine whether it can represent the preorder traversal of a Binary Search Tree (BST).

BST Property

Left subtree contains values smaller than the root.
Right subtree contains values greater than the root.

Preorder Traversal

The preorder traversal follows the order:

Root → Left → Right

Example 1

Input:

arr = [2, 4, 3]

Output:

true

Explanation:

The array represents the preorder traversal of the following BST:

Preorder:

2 → 4 → 3

Example 2

Input:

arr = [2, 4, 1]

Output:

false

Explanation:

After moving to the right subtree of 2, we cannot encounter a value smaller than 2. Since 1 appears after 4, it violates the BST property.

Approach

A stack is used to simulate the traversal.

Key Idea

Maintain two things:

Stack → Stores the path from the root to the current node.
lowerBound → Represents the minimum value that future nodes must have.

Initially,

lowerBound = Integer.MIN_VALUE;

Whenever we move to the right subtree, the parent becomes the new lower bound.

If any future value is smaller than this lower bound, the preorder sequence is invalid.

Algorithm

For every value in the array:

Step 1

value < lowerBound

return false.

This means we are trying to place a node in a position where BST rules are violated.

Step 2

While

value > stack.peek()

Pop elements from the stack.

The last popped element becomes the new lower bound because we are entering its right subtree.

Step 3

Push the current value into the stack.

Step 4

If every element is processed successfully,

return true.

Java Code

import java.util.*;

class Solution {
    public boolean canRepresentBST(List<Integer> arr) {

        Stack<Integer> stack = new Stack<>();

        int lowerBound = Integer.MIN_VALUE;

        for (int val : arr) {

            // If current value is smaller than allowed value
            if (val < lowerBound) {
                return false;
            }

            // Moving towards right subtree
            while (!stack.isEmpty() && val > stack.peek()) {
                lowerBound = stack.pop();
            }

            stack.push(val);
        }

        return true;
    }
}

Code Explanation

Creating the Stack

Stack<Integer> stack = new Stack<>();

The stack stores the ancestors of the current node.

Example:

Stack:

8
5
1

Initializing the Lower Bound

int lowerBound = Integer.MIN_VALUE;

Initially, there is no restriction.

Any integer is allowed.

Traversing Every Element

for (int val : arr)

Process every node in preorder.

Checking BST Violation

if (val < lowerBound)
    return false;

Suppose

lowerBound = 8

and the current value is

Since

5 < 8

the node is appearing in the right subtree of 8, which is impossible.

Hence,

return false;

Moving to the Right Subtree

while (!stack.isEmpty() && val > stack.peek()) {
    lowerBound = stack.pop();
}

This is the most important part.

Suppose the preorder is

8 5 1 7

Current stack:

8
5
1

Current value:

Since

7 > 1

Pop:

lowerBound = 1

Stack:

8
5

Again,

7 > 5

Pop:

lowerBound = 5

Stack:

Now,

7 < 8

Stop.

Now every future node must be greater than 5 because we entered the right subtree of node 5.

Push Current Node

stack.push(val);

The current node becomes part of the traversal path.

Return True

return true;

No BST rule was violated.

Dry Run

Example

arr = [8, 5, 1, 7, 10, 12]

Current	Stack	Lower Bound
8	8	-∞
5	8, 5	-∞
1	8, 5, 1	-∞
7	8, 7	5
10	10	8
12	12	10

No violations occur.

Answer: true

Invalid Example

arr = [8, 5, 1, 10, 7]

Current	Stack	Lower Bound
8	8	-∞
5	8, 5	-∞
1	8, 5, 1	-∞
10	10	8
7	—	8

Since

7 < 8

the preorder is invalid.

Answer: false

Why Does This Work?

Whenever we pop from the stack, we are leaving the left subtree and entering the right subtree of that node.

Once we enter a right subtree, no future node can be smaller than that node.

The lowerBound variable keeps track of this restriction. If any value violates it, the sequence cannot represent the preorder traversal of a BST.

Complexity Analysis

Complexity	Value
Time	O(n)
Space	O(n)

Why O(n)?

Every element is pushed onto the stack exactly once.
Every element is popped from the stack at most once.

Therefore, the total number of stack operations is at most 2n, resulting in O(n) time complexity.

Summary

This approach efficiently verifies whether a given array can represent the preorder traversal of a Binary Search Tree by using a stack to simulate traversal and a lowerBound variable to enforce BST constraints. Each element is processed only once, making the algorithm run in O(n) time with O(n) auxiliary space while correctly identifying both valid and invalid preorder sequences.