Having Fun with BST #2

                 Binary Search Tree Problems (#2)  

After we covered how to traverse a BST, we will go head to try some different problems about BST now ! 

          1. Valid Binary Search Tree 

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   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3 

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

-----------------------------------------------------------------------------------------------------------------------

Analyze: What is the first solution comes to your mind ? 

Solution 1: If you still remember the 5 basic ways we traverse a BST, you will find a straightforward way to do it --> 1. Do a inOrder traversal. 2. See if you get a ascending order sequence. 

The code will be very similar to what we did on a inOrder traversal: 

Solution 2: Here is a more elegant approach: 

This approach is based on the definition of BST that the values in left subtree will smaller than current node and the values in right subtree will greater than current node. We narrow the scope every time call the recursive function isValid. 

Can you come up solution 3 ? 

     2. Binary Search Tree Iterator 

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.

--------------------------------------------------------------------------------------------------------------------------

QUIZE: Do you know which data structure we will use in this problem ?  ( Hint: Consider the relationship between this problem and  In Order traversal) 

Analyze: The idea is very similar to the iterative way to do a in order traversal, because a iterator actually will return the values in the BST in ascending order. 

So we keep a stack and make sure the smallest value is in the top of this stack. 

       3. In-order Successor in BST 

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

-----------------------------------------------------------------------------------------------------------------------

Analyze: In order successor should be the next value that bigger than current node's value.  There are 2 cases we need to consider : 1: this node has right child. 2. this node do not have a right child. 

For the first case, we simply find the Min value in its right sub-tree. 

For the second case, we need to keep going upwards to search its parents, until we find the first parents that is bigger than its value ( or there is no successor exist) 

      4. Kth Smallest Element in a BST 

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

-----------------------------------------------------------------------------------------------------------------------

Analyze:  The most elegant way to solve this question will utilize the property of BST. We actually covered this question in the we want Kth element , but it is good for us to practice again :-) 

There are so many questions about BST that I can't cover all of them, but recursive method, the property of BST are two keys to remember when you solving them. Hope this two article give you a pretty good start point to discover more about BST. 

Happy Coding^^ 

Ye Jiang