# 98. Validate Binary Search Tree

Reference: LeetCode EPI 7.1

Difficulty: Medium

## Problem

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 |

**Follow up:** $O(1)$ Space? No. Iteration methods need stacks too.

## Analysis

**Methods:**

The naive approach would be to calculate the `lower`

and `upper`

values when visiting each node, but it turns out to be very inefficient because it does a lot of repeated calculation. In the worst case, time complexity would be $O(N^2)$.

One alternative might be to cache the largest and smallest keys at each node using a HashMap, which requires $O(N)$ additional storage for the cache.

- Recursion
- For a node $x$, all nodes in its left subtree should be satisfy the constraint
`[L, x.val)`

and all nodes in the other side should be satisfy`(x.val, R]`

. **Time:**$O(N)$ since we visit each node exactly once.**Space:**- Best: $O(\log{N})$ when the tree is bushy.
- Worst: $O(N)$

- For a node $x$, all nodes in its left subtree should be satisfy the constraint
- Iteration
- The above recursion could be converted into iteration with the help of three stacks.
**Time:**$O(N)$**Space:**$O(N)$

- Inorder Traversal
- We can use the fact that an inorder traversal visits keys in sorted order. We can compare each node we visit with the previous node during the inorder traversal.
- Recursion
- Iteration

**Time:**$O(N)$**Space:**$O(N)$ or $O(\log{N})$

- We can use the fact that an inorder traversal visits keys in sorted order. We can compare each node we visit with the previous node during the inorder traversal.
- BFS Manner
- When the property is violated at a node whose depth is small (close to the root), we can use this manner. Specifically, we use a queue, where each queue entry contains a node, as well as an upper bound and a lower bound on the keys.
**Time:**$O(N)$**Space:**$O(N)$

## Code

**Test Case:**

1 | [2,1,3] |

### Recursion

**Note:**

- Use
`Long.MIN_VALUE`

rather than`Integer.MAX_VALUE`

. But it’s better to use`null`

. - Be careful of the traversal order. When invalidity is detected, we should return immediately.
- Notice the condition of the problem description:
`Equality`

is not allowed.

**My original bad code:**

It is not efficient because it is a `postorder`

traversal. If `isValid`

is `false`

, we should return immediately.

1 | public boolean isValidBST(TreeNode root) { |

**Improvement:**

1 | private boolean isBSTHelper(TreeNode x, long lower, long upper) { |

**More Improvement:**

**Note:** Rather than using extreme constants, we can use `null`

and modify the conditions.

1 | public boolean isValidBST(TreeNode root) { |

### Iteration

**Note:**

- Check the stack before pushing values into it.

1 | Stack<TreeNode> stack = new Stack<>(); |

### Inorder Traversal

#### Recursion

1 | public boolean isValidBST(TreeNode root) { |

#### Iteration

1 | private boolean inorderItr(TreeNode root) { |