Leetcode - find if BST is valid or not Given a binary tree, determine if it is a valid binary search tree
  (BST).
  
  Assume a BST is defined as follows:
  
  The left subtree of a node contains only nodes with keys less than the
  node's key. The right subtree of a node contains only nodes with keys
  greater than the node's key. Both the left and right subtrees must
  also be binary search trees.


Example 1:

  2
   / \
  1   3

Input: [2,1,3]
Output: true


Example 2:

 5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.


My solution


Do inorder traversal and keep it in stack.
Iterate through stack to see if any of the value on top is less than equal to second top. 


Definition for a binary tree node.

 public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
  }




class Solution {

    public void doInOrderTraversal(TreeNode root, Stack s) {
        if(root == null) {
            return;
        }
        doInOrderTraversal(root.left, s);
        s.push(root.val);
        doInOrderTraversal(root.right, s);

    }

    public boolean isValidBST(TreeNode root) {

        if(root == null) {
            return true;
        }

        Stack&lt;Integer&gt; stack = new Stack&lt;&gt;();

        doInOrderTraversal(root, stack);

        while(!stack.isEmpty()) {
            int top = stack.pop();
            if(stack.isEmpty()) {
                return true;
            }
            int secondTop = stack.peek();
            if(top &lt;= secondTop) {
                return false;
            }
        }
        return true;
    }
}


I was thinking to not use stack, but two values current and previous. And keep check if current is less than previous then only break. I am not sure, how to do this. Please suggest.
Your solution:

seems legit :)
One thing I'd suggest here is to use ArrayDeque instead of Stack

Another possible solution:

Basically, for every subtree we have constrain, that every node in it should be in range (X, Y).

For root this range will be (-inf; +inf) - in other words, there could be any value in root.

For root's left subtree range will be (-inf, value-in-root), for right - (value-in-root, +inf).

Last thing - on each iteration we should check, that value in node is within this range, like so:

public boolean doInOrderTraversal(TreeNode root, int min, int max) {
    if (root == null) {
        return true;
    }
    if (root.val &lt;= min || root.val &gt;= max) {
        return false;
    }

    return doInOrderTraversal(root.left, min, root.val) &amp;&amp; doInOrderTraversal(root.right, root.val, max);
}