# My java inorder iteration solution

• the idea is to do a inorder Traversal and keep the value of the

``````public boolean isValidBST (TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode> ();
TreeNode cur = root ;
TreeNode pre = null ;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left ;
} else {
TreeNode p = stack.pop() ;
if (pre != null && p.val <= pre.val) {
return false ;
}
pre = p ;
cur = p.right ;
}
}
return true ;
}``````

• Using iterative inorder traversal is cool, although cost O(logN) space， its still a good solution.

• If duplicates are allowed, say right child is larger than or equal to the parent, how about that?

• it is not allowed in the problem

• This post is deleted!

• How did you come up this idea? Could you explain more?

• Could you explain why the space is O (logN)? I think it is O(n), since it puts all nodes (both left and right nodes) in the stack.

• Actually I think it's allowed in the test case 64 which has the input (1,1)

• it is obviously not O(logN) space , it's O(N) space and time

• This post is deleted!

• @xjq It's O(lgn) if the tree is well balanced.

• @zhu15 in fact, you have to visit every node in the tree, so it's O(N) time.

• @xjq I was talking about space complexity.

• @zhu15 ok, but you can not guarantee it's always balanced in all cases, so it's O(N) space.

• This post is deleted!

• @zhu15 oh, in fact, the worst case of binary search is Log(N) + 1 comparisons at most.

• @xjq Yeah, that's why I deleted that post. A proper example is quick sort. The worst case is O(n^2) and according to the way you put that quick sort is just an O(N^2) algorithm which sounds funny.

• @zhu15 oh yes, the average space complexity is O(height), which can be as low as logN.

• @zhu15 and average is indeed LogN. thanks for pointing out this.

• Share:

``````public boolean isValidBST(TreeNode root) {
if(root ==  null) return  true;
return helper(root.left, null, root.val) && helper(root.right, root.val, null);
}

private boolean helper(TreeNode node, Integer loBound, Integer hiBound){
if(node == null) return true;
if(loBound != null && node.val <= loBound) return false;
if(hiBound != null && node.val >= hiBound) return false;
return helper(node.left, loBound, node.val) && helper(node.right, node.val, hiBound);
}``````

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