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:

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.

1. 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)$
2. Iteration
• The above recursion could be converted into iteration with the help of three stacks.
• Time: $O(N)$
• Space: $O(N)$
3. 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})$
4. 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:

### 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.

It is not efficient because it is a postorder traversal. If isValid is false, we should return immediately.

Improvement:

More Improvement:

Note: Rather than using extreme constants, we can use null and modify the conditions.

### Iteration

Note:

• Check the stack before pushing values into it.

### Inorder Traversal

#### Iteration

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.