# 173. Binary Search Tree Iterator

## Description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling `next()` will return the next smallest number in the BST.

Note: `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

We need a Stack to help us to save the next smallest number.

In a Binary Search Tree, The most left node is the minimum. So we can save each left node from root in a stack and get the minimum left node.
So the function `hasNext()` just return !stack.isEmpty();
And every time we use `next()`,we pop the stack, and push all left nodes of the pop node’s right node.
So code is following.

# 98. Validate Binary Search Tree

## Description

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:

Binary tree `[2,1,3]`, return true.
Example 2:

Binary tree `[1,2,3]`, return false.

The basic method is to use a inorder traversal, because in a BST the left always less than the right.

I design a recursion to solve the problem.

# 108. Convert Sorted Array to Binary Search Tree

## Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST