To check if array represents preorder traversal of a binary tree

Share

Problem: For a given array of numbers, check if it represents preorder traversal of a binary search tree.

Problem Explanation:

Input: arr={51, 41, 45, 81, 111}, it represents preorder traversal of binary search tree below

     51
   /   \
 41    81 
  \      \
  45     111

Output: True

Input: arr={20, 25, 1}, it represents the tree below which is not a binary search tree

    20
     \
      25
     /
    1

Output: False

Java Implementation

public class IsBSTRepresentation {
    boolean isBSTRepresentation(int[] arr) {
        Stack<Integer> stack = new Stack<Integer>();
        int root = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < root) {
                return false;
            }

            while (!stack.empty() && (Integer) stack.peek() < arr[i]) {
                root = (Integer) stack.peek();
                stack.pop();
            }
            stack.push(arr[i]);
        }
        return true;
    }

public static void main(String[] args) {

        IsBSTRepresentation isBSTRepresentation = new IsBSTRepresentation();
        System.out.println(isBSTRepresentation.isBSTRepresentation(new int[]{20, 25, 1}));

    }
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)