Java O(n) and O(1) extra space


  • 230

    Solution 1

    Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Stack<Integer> path = new Stack();
        for (int p : preorder) {
            if (p < low)
                return false;
            while (!path.empty() && p > path.peek())
                low = path.pop();
            path.push(p);
        }
        return true;
    }
    

    Solution 2 ... O(1) extra space

    Same as above, but abusing the given array for the stack.

    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE, i = -1;
        for (int p : preorder) {
            if (p < low)
                return false;
            while (i >= 0 && p > preorder[i])
                low = preorder[i--];
            preorder[++i] = p;
        }
        return true;
    }
    

    Solution 3 ... Python

    Same as solution 1, just in Python.

    def verifyPreorder(self, preorder):
        stack = []
        low = float('-inf')
        for p in preorder:
            if p < low:
                return False
            while stack and p > stack[-1]:
                low = stack.pop()
            stack.append(p)
        return True

  • 0

    Hi, Stefan. Nice codes, as your usual style :-) A little question, I wonder if it is possible to solve this problem in also O(1) additional space but without modifying preorder?

    BTW, could I ask that why you use Jave this time, instead of your Python :-)


  • 0

    Python doesn't have expressions like i-- and ++i. It can do i -= 1 and i += 1, but these are statements and can't be used inside other expressions. Solution 1 is nicer in Python, but I wanted to show it together with solution 2 and use the same language. Also, among these latest problems, Java seems to be the most popular language.

    Oh well, I have added a Python version of solution 1 now.


  • 0

    The stack[-1] is really nice :-) Well, it seems that Python even does not need to have an explicit stack?


  • 1

    I'm not sure about O(1) extra space without modifying preorder, but I think it's impossible. As someone recently pointed out, that only works for regular languages, and this problem's language doesn't seem regular to me. Let's use each number as a character (i.e., ignoring that the alphabet should be finite) and use the Myhill–Nerode theorem. Consider the words xi = [3i, 3i+1] for all integers i. Now for words xi != xj, the extension [3*min(i,j)+2] distinguishes them. For example, you can append [5] to [3,4] but not to [6,7]. So there are infinitely many pairwise distinguishable words, thus infinitely many equivalence classes, and thus the language isn't regular.

    Not sure I did this fully properly, though :-)


  • 0

    Hi, Stefan. Well, I am totally shocked. So you are using some knowledge of theoretical computer science, like complexity class and regular language. Well, I guess that you mean only regular languages will allow for O(1) space solution. For the remaining parts, I am just confused: no idea of where comes the language and how to apply it to this problem. Well, I need to learn more :-)


  • 1

    Yeah, it's a bit theoretical. I didn't study comp-sci for nothing, must be good for something :-)

    A "language" is just a set of certain "words". A word here is an input sequence, and the language is all those words (input sequences) that are valid BST preorder sequences. For example, [3,4,5] is a word in the language and [6,7,5] is a word not in the language.


  • 0

    Thanks for this nice explanation. I now get some intuition about it :-)


  • 0
    F

    Hi Stefan,

    The solution will also return true for both inorder traversal and postorder traversal in the same BST. For example, in the following BST:

          6
        /   \
      2     7
     / \   
    1   3
    

    The algorithm will return true for all three tree traversals.

    Thanks


  • 0

    @fan22 Sorry, I don't get your point. Partly because that's rather a property of the problem, not so much a property of a solution. Though you're wrong about postorder. For example, the postorder of

    1
      \
        3
       /
      2
    

    is [2, 3, 1], which isn't a valid preorder. For inorder you're correct, every valid inorder is also a valid preorder.


  • 0
    F

    Hi Stefan,

    Thanks for the reply. You are right, I believe this is a property of the problem but not the solution. The solution is very succinct and correct, sorry that I didn't make it clear!


  • 0

    Thanks for clarifying... I indeed wasn't sure whether you meant it's interesting or that there's something wrong :-)


  • 0
    M

    pretty amazing elegant solution. A lot easier to generate a preorder traversal using a stack while doing this way is a harder. thanks!


  • 0
    T

    Hello,

    I like this algorithm, but I think it is hard at least for me to understand. I want to share my understanding, if wrong, please point it out.

    In short, to construct the bst with the sequence, for each element, we shall make sure, when smaller elements come, it is okay, but when there is a bigger one come, then all following elements must be bigger.


  • 2
    5

    Hi Stefan, your solution is always amazing.
    But I am also wondering how to verify postorder sequence. Could you give me some hint?
    Thank you.


  • 0
    H
    This post is deleted!

  • 0

    Well, preorder sequence has the order of root - left - right while postorder sequence has the order of left - right - root. The only difference is that root now appears at the end instead of at the beginning. I do not look into it too much but I guess there would be a lot of similarities in the algorithms.

    You may refer to this stackoverflow discussion if you need.


  • 5
    I

    To answer @516364598chang question about post-order. Using @StefanPochmann's solution.

    public static bool IsValidPostOrderBst(int[] nums)
            {
                int i = nums.Count();
                int root = int.MaxValue;
                for (int j = nums.Count() - 1; j >= 0; j--)
                {
                    if (nums[j] > root) return false;
                    while (i <= nums.Count() - 1 && nums[j] > nums[i])
                        root = nums[i++];
                    nums[--i] = nums[j];
                }
                return true;
            }

  • 0

    Better post this as a comment under 516364598chang's answer so he/she gets notified about it. Or write a comment there saying to look at your answer.


  • 11

    same logic, use one more stack to be easier to understand
    Basically this is how to recover inorder sequence from preorder sequence of a BST.

    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> inorder = new Stack<>();
        
        for(int v : preorder){
            if(!inorder.isEmpty() && v < inorder.peek())
                return false;
            while(!stack.isEmpty() && v > stack.peek()){
                inorder.push(stack.pop());
            }
            stack.push(v);
        }
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.