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 3Input:[2,1,3]Output:true

**Example 2:**

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

## Basic knowledge

## Solution

We can solve this problem by doing inorder traversal in iterative way.

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public bool IsValidBST(TreeNode root) { if(root == null) return true; TreeNode pre = null; Stack<TreeNode> s = new Stack<TreeNode>(); while(root != null || s.Count > 0) { while(root != null) { s.Push(root); root = root.left; } root = s.Pop(); if(pre != null && pre.val >= root.val) return false; pre = root; root = root.right; } return true; } }

Time Complexity: O(n)

Space Complexity: O(n)