Checking if given preorder traversal is valid BST

Question

I was writing code to check from preorder traversal if it is a valid BST. e.g preorder traversal 1,2,4,3,5 is valid BST while 1,3,4,2 is not

I built whole tree from that preorder sequence and then checked if that tree is a valid BST. This is O(N) solutions with respect to both space and time complexity.

Does anybody have good approach than this? I have intuition that we can do this in O(1) extra space.

Answer 1

Checking whether a permutation of 1..n is a preorder of a valid BST (that BST, if it exists, is unique; imreal's answer is not a counterexample because the second reconstruction is not sorted) is equivalent to testing whether that permutation is stack-sortable, i.e., avoids the 231-pattern. I can't seem to find any linear-time constant-space algorithm under any of these names, which would tend to suggest given the amount of attention that this problem has attracted that no one knows of a constant extra space solution.

If you're willing to assume a read/write input that can be destroyed, then there's a linear-time algorithm that uses constant extra space. It's not necessary to reconstruct the tree separately and then test it. Here's some Python to that effect.

def isbstpreorder(iterable):
    lowerbound = None
    stack = []
    for x in iterable:
        if lowerbound is not None and x < lowerbound: return False
        while stack and stack[-1] < x: lowerbound = stack.pop()
        stack.append(x)
    return True

To eliminate the separate storage for the stack, store it in a prefix of the input list.

Answer 2

The idea is to check if the input array can be divided into two sub arrays representing the left and the right sub tree. Obviously, this has to be done recursively.

Here's some tested Java code to illustrate the same:

import java.util.ArrayList;
import java.util.List;


public class PreOrderBSTCheck {

    /**
     * @param args
     */
    public static void main(String[] args) {

        String ipStr = "1 4 2 3";
        String[] ipArr = ipStr.split(" ");

        int[] intArr = new int[ipArr.length];
        List<Integer> listArr = new ArrayList<Integer>();

        for(int i = 0 ; i < ipArr.length ; i++)
        {
            intArr[i] = Integer.parseInt(ipArr[i]);
            listArr.add(intArr[i]);
        }
        //System.out.println("List size: "+listArr.size());
        if(checkTree(listArr))
            System.out.println("Valid");
        else
            System.out.println("Invalid");
    }

    public static boolean checkTree(List<Integer> arr)
    {
        if(arr.size() == 1)
        {
            return true;
        }

        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        Integer root = arr.get(0);
        int idx = 1;

        //adding left subtree nodes
        while(arr.get(idx) < root)
        {
            left.add(arr.get(idx++));

            if(idx >= arr.size())
                break;
        }

        //adding right subtree nodes
        if(! (idx >= arr.size()))
            while(arr.get(idx) > root)
            {
                right.add(arr.get(idx++));

                if(idx >= arr.size())
                    break;
            }

        if(left.size() + right.size() == arr.size() - 1)
        {
            if(left.size()==0)
            {
                return true && checkTree(right);
            }
            else if(right.size() == 0)
            {
                return true && checkTree(left);
            }
            else
            {
                return checkTree(left) && checkTree(right);
            }
        }
        else
        {
            return false;
        }

    }

}