Print leaf nodes from preorder traversal of BST

JavaView on GFG

Time: O(n)

Space: O(n)

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?