Return to Answer

The algorithm is a constant-memory – it does not use a stack, it just iterates through the right-most branch of the tree while merging left subtrees into it.

The algorithm is constant-memory and linear-time – it does not use a stack, it just iterates through the right-most branch of the tree while merging left subtrees into it.

...you can also get rid of the stack by transforming your tree into a list – it's the first stage of the Day-Stout-Warren algorithm to balance a BST.

...you can also get rid of the stack by transforming your tree into a list – it's the first phase of the Day-Stout-Warren algorithm to balance a BST.

Here is an example of a full recursive test without an explicit stack.

A left subtree of any node has values bounded from above by that node, similarly a right subtree has values bounded from below. It follows that any subtree is bounded by its closest left- and right-side ancestors (except the left-most branch, which has no left-side ancestor, and the right-most branch, which has no right-side ancestor; and a special case of the root node, which has no ancestor at all).

class Solution {
 
 public boolean isValidBST(TreeNode root) {
 return isValidBST(null, root, null);
 }
 private boolean isValidBST(TreeNode leftAncestor, TreeNode node, TreeNode rightAncestor) {
 // base case
 if (node == null)
 return true;
 // bounds by ancestors (duplicated keys not allowed; replace
 // <= and >= with < and >, respectvely, to allow duplicates)
 if (leftAncestor != null && node.val <= leftAncestor.val)
 return false;
 if (rightAncestor != null && node.val >= rightAncestor.val)
 return false;
 // this node valid - validate its subtrees; this node becomes
 // the closest right-side ancestor for its left subtree
 // and the closest left-side ancestor for its right subtree
 return
 isValidBST(leftAncestor, node.left, node) &&
 isValidBST(node, node.right, rightAncestor);
 }
}

Your code is correct and IMHO optimal for the algorithm it implements.
The only two details I would recommend to change are:

• rename the node member val to value – there's no reason to strip the last two characters,
• and make the doInOrderTraversal method private – it seems useful inside this Solution only.

What concerns the algorithm: yes, you can reach the same result without the additional Stack object. Here is an example of a full recursive test without an explicit stack.

A left subtree of any node has values bounded from above by that node, similarly a right subtree values are bounded from below. It follows that any subtree is bounded by its closest left- and right-side ancestors (except the left-most branch, which has no left-side ancestor, and the right-most branch, which has no right-side ancestor; and a special case of the root node, which has no ancestor at all).

class Solution {
 
 public boolean isValidBST(TreeNode root) {
 return isValidBST(null, root, null);
 }
 private boolean isValidBST(TreeNode leftAncestor, TreeNode node, TreeNode rightAncestor) {
 // base case
 if (node == null)
 return true;
 // bounds by ancestors (duplicated keys not allowed; replace
 // <= and >= with < and >, respectvely, to allow duplicates)
 if (leftAncestor != null && node.val <= leftAncestor.val)
 return false;
 if (rightAncestor != null && node.val >= rightAncestor.val)
 return false;
 // this node valid - validate its subtrees; this node becomes
 // the closest right-side ancestor for its left subtree
 // and the closest left-side ancestor for its right subtree
 return
 isValidBST(leftAncestor, node.left, node) &&
 isValidBST(node, node.right, rightAncestor);
 }
}

At the cost of additional conditions (which obfuscate the code a bit) you can save about a half of recursive calls:

 public boolean isValidBST(TreeNode root) {
 return (root == null) || isValidBST(null, root, null);
 }
 private boolean isValidBST(TreeNode leftAncestor, TreeNode node, TreeNode rightAncestor) {
 assert node != null;
 // bounds by ancestors (duplicated keys not allowed; replace
 // <= and >= with < and >, respectvely, to allow duplicates)
 if (leftAncestor != null && node.val <= leftAncestor.val)
 return false;
 if (rightAncestor != null && node.val >= rightAncestor.val)
 return false;
 // this node valid - validate its subtrees; this node becomes
 // the closest right-side ancestor for its left subtree
 // and the closest left-side ancestor for its right subtree
 return
 (node.left == null || isValidBST(leftAncestor, node.left, node)) &&
 (node.right == null || isValidBST(node, node.right, rightAncestor));
 }