Print leaf nodes from preorder traversal of BST

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Given preorder traversal, identify and print leaf nodes of the BST without constructing the tree.

Intuition

Given preorder traversal, identify and print leaf nodes of the BST without constructing the tree.

Algorithm

1Simulate BST insertion using stack. A node is a leaf if no subsequent node falls in its value range as left/right child.

Common Pitfalls

• Use stack to track valid range at each position. A preorder element with no children in both directions is a leaf.

Print leaf nodes from preorder traversal of BST.java

Java

// Approach: Simulate BST insertion using a stack-based preorder traversal to identify leaf nodes.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> leafNodes(int[] preorder) {
        ArrayList<Integer> result = new ArrayList<>();

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

        int n = preorder.length;

        for (int i = 0; i < n - 1; i++) {
            int curr = preorder[i];
            int next = preorder[i + 1];
            boolean isLeaf = false;

            if (next < curr)
                stack.push(curr);
            else {
                while (!stack.isEmpty() && next > stack.peek()) {
                    stack.pop();
                    isLeaf = true;
                }

                if (isLeaf)
                    result.add(curr);
            }
        }

        result.add(preorder[n - 1]);

        return result;
    }
}

Was this solution helpful?