Topic 3: Binary Search Trees

Questions to be answered:

1. How to check tree is balanced?

2. Number of internal nodes, external nodes, and height.

Todos:
1. binary search tree deletion.

Binary search tree property:

"Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key." 

Operation related to Binary Search Tree:

1. Inorder-Tree-Walk (recursive)
   
2. Preorder-Tree-Walk 
1. put the print x.key before the recursive calls.
3. Postorder-Tree-Walk 
1. put the print x.key after the recursive calls.
4. Search(recursive)
   
5. Search(iterative)
   
6. Minimum
   
7. Maximum
   
8. Successor
   
1. Two case observed, 
1. If successor exist and x's right sub-tree is not NUL, we find the minimum node of the right sub-tree.
2. If successor exist and x don't have a right sub-tree, it's successor must be in the ancestors, which is above the x in the tree. Its successor in this case can be found as the lowest (first when we track back from bottom up) ancestor who has the left children is also x's ancestor. (for instance, the node 13's successor is 15 in the following tree)
   
9. Predecessor
1. Similar to the successor, two cases:
1. If the left sub-tree exist, find the maximum of the left sub-tree, which is the predecessor of the node.
2. If the left sub-tree doesn't exist, the predecessor is the first ancestor that has a right child which is also its ancestor. 
10. Insertion
    
1. Two point to notice:
1. y is defined to keep a copy of the x's parent pointer, it also called trailing pointer. Because by the time the NUL is found for z, x already become NUL, only its previous(save at y) can be used to update with z.
2. x is defined as a pointer to find the proper position in the tree. View it as a pinter that used to visit the tree node to find something.
11. Deletion
    
1. Deletion is non-trivial, there are three cases: 
1. z has only one child, just remove the node, this will not impact the property of Binary search tree.
2. z has two children and its successor y is z's right children, replace z by y.
3. z has two children and its successor y is not z's right children. In this case, we still need to replace z by y, but it involves more operations. We need re-arrange the node in the z's right sub-tree in order to maintain the binary search tree property. I can be proved that z's successor y doesn't have a left sub-tree. So we do the following: (1) move y out of the right sub-tree, transplant its right sub-tree to y, notice this doesn't violate the tree properties. (2) replace z by y, update y's right sub-tree with z's right sub-tree. update y's left sub-tree with z's left sub-tree to complete the "delete operation". Notice this second step still keep the tree as a valid binary search tree.  (If you don't understand, see CLRS page 297 Figure 12.4)
   
12. Transplant
    
1. this is function is to replace the sub-tree rooted at node u with the sub-tree rooted at node v, node u's parent becomes node v's parent. Pay attention to update v's parent with v.p = u.p if v is not NUL. if it is, we don't need to do anything, replace u with a NUL will do the all.

How to build a balanced binary search tree?

Solving Real Tree Problems

1. Write a iterative method to do in-order traversal of a Binary Tree. Use two solution, solution 1 can use stack. In solution 2, stack is not allowed.
   Thoughts:
   
   
   1. Using loops to do the iterative, stack is used as a temp storage.
   2. First node to visit is left most node in the tree. It don't have any left nodes.
   3. End the loop when the largest node has been visited (in-order), the largest nodes in the right most.
   4. Algorithm: Visit the left most node first, two possibilities exist: (1) it have no children, (2) it have right children. If it have no children, visit it --> visit parents --> go to its parent's right children.
   5. BE CAUTIONS about the if condition correctness.
   
   The non-stack solution can rely on pointer that can visit its parents and its grandparents after visit the right children. This is straight forward to think but hardest to implement.
   
   The full solution to this problem can find here: http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html 
2. untitled