# Simple Recursive O(1) Memory

• Although this solution has a stack, the stack will always have only one item pointing to the previous node in ascending sequence.

``````public bool IsValidBST(TreeNode root)
{
// use inorder traverse to put treenode to ascending order
Stack<TreeNode> stack = new Stack<TreeNode>();
return InorderBST(root, stack);
}

public bool InorderBST(TreeNode root, Stack<TreeNode> stack)
{

if (root == null)
return true;

if (root.left != null)
{
if (!InorderBST(root.left, stack)) return false;
}

// visit the node
if (stack.Count() > 0) // if there is item in stack
{
TreeNode node = stack.Pop();
if (node.val >= root.val) return false;
}
stack.Push(root);

if (root.right != null)
{
if (!InorderBST(root.right, stack)) return false;
}

return true;
}
``````

If you are using C#, you can eliminate the need of stack by replacing with the ref treeNode to point to the previous.

``````public bool IsValidBST(TreeNode root) {
// use inorder traverse to put treenode to ascending order
// ref value to point to previous
TreeNode prev = null;
return InorderBST(root, ref prev);
}

public bool InorderBST(TreeNode root, ref TreeNode prev) {
if(root == null)
return true;

if(root.left != null)
{
if(!InorderBST(root.left, ref prev)) return false;
}

// visit the node
if(prev!= null)
{
if(prev.val>= root.val) return false;
}
prev=root;

if(root.right != null){
if(!InorderBST(root.right, ref prev)) return false;
}

return true;
}``````

• This is not O(1) because the recursive runtime stack will take O(h) memory.

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