Verify Preorder Sequence in Binary Search Tree

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	43 MB
Date	2021-12-09

Solution

public class Solution {
    public bool VerifyPreorder(int[] preorder) {
        Stack<int> stack = new Stack<int>();
    Stack<int> inorder = new Stack<int>();

    foreach(var v in preorder)
    {
        if (inorder.Count != 0 && v < inorder.Peek())
            return false;
        while (stack.Count != 0 && v > stack.Peek())
        {
            inorder.Push(stack.Pop());
        }
        stack.Push(v);
    }
    return true;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed