Chapter 12: Binary Search Trees

12.1.1. Try it yourself.

12.1.2. BST and Min-Heap property differs in the relationship of their key field with their childs. They also differ in the organization of their nodes, meaning for min-heap (or for that matter max-heap, we're dealing with binary heaps only) is always filled on all levels except possibly the last. Heaps can be viewed as a complete binary tree but not our BST it can also be an incomplete binary tree.
            BST: For every node x with left child 'l' and right child 'r', following is the relationship between their keys:     key[x] >= key[l] and key[x] <= key[r].
            Min-Heap:  For every node x with left child 'l' and right child 'r', following is the relationship between their keys:     key[x] <= key[l] and key[x] <= key[r].
            We can certainly use a min-heap to print the keys in sorted order. But, the time will be O(nlog(n)). Heap-sort actually uses a min-heap to sort the values.

12.1.3. I'm just writing a pseudo-code:
      1. Create an empty stack.

      2. Initialize current node as root.

      3. Push the current node to stack and set current = current->left until current is NULL.
      4. If current is NULL and stack is not empty then
               a. Pop the top item from stack.
               b. Print the popped item, set current = current->right
               c. Go to step 3.
       5. If current is NULL and stack is empty then we are done.

       (copied from here)

       

      There is also another way of doing in-order walk without a stack. I'll try to post this as well.

12.1.4. PRE-ORDER-WALK:

            

           Pre-Order-Walk(x)

                  if(x != NULL)

                        then

                              print key[x]

                              Pre-Order-Walk(x->left)

                              Pre-Order-Walk(x->right)

           POST-ORDER-WALK:

            
           Post-Order-Walk(x)
                  if(x != NULL)
                        then
                              Post-Order-Walk(x->left)
                              Post-Order-Walk(x->right)
                              print key[x]

12.1.5. This is just a plain argument. First think about constructing a BST from a given set of n-elements. You've to order the elements satisfying the BST property. 
            Now, if the given set of n-elements is sorted ( O(nlogn) ) worst case, we can construct a BST by always choosing a mid-element as the root and dividing the list in two halves, and making mid-element of left half as left child of the root and mid-element of right half as right child of root. Repeating this procedure till the halves are empty. This can be easily done in O(n) complexity if       we've an array holding the n-elements. Things would be much different and a little complicated if we've those sorted elements in a linked-list.
             Thus, the overall complexity would be O(nlogn) + O(n) which is O(nlogn) as it is the dominating term here.
                 
12.2.1. Try it yourself.

12.2.2. 
           Tree-Minimum(x)
                 if( ! x->left)
                     return Tree-Minimum(x->left);
                 return x;

           Tree-Maximum(x)
                 if( ! x->right)
                     return Tree-Maximum(x-> right);
                 return x;

12.2.3. 
           Tree-Predecessor(x)
                if( ! x->left)
                    return Tree-Maximum(x->left);
                y = x->parent;
                while ! y && x == y->left
                         x = y;
                         y = y->parent;
                 return y;
12.2.4. 
                                   5
                                          8
                                     7         9

                 Search for 9 in this tree. Then A = {7}, B = {5, 8, 9} and C={}.  So, since 7 > 5 it breaks professor's claim.

12.2.5. Argument for successor:
           Suppose 'x' is the node and it's successor is 's'. Then key[s] should be the smallest key which is larger than key[x]. As given node 'x' has two child. So, successor of 'x' should be the node with smallest key in the right subtree. The smallest key for any tree with root 'r' doesn't have a left child, this you can verify by looking at Tree-Minimum function.

12.2.6. 

12.2.7. Inorder-tree-walk effectively does the same thing by exhausting the left subtree to find min, and discovering successors by minimizing right subtrees, or ascending to first-right parents thanks to the recursive stack.

The procedures are equivalent and both run in Theta(n). [Copied]

12.2.8. 

12.2.9. First case will be when x is the left child of y. It implies:
            
            1. key[y] > key[x] && key[x] < key[ancestor_of_y]
            2. key[y] < key[nodes_in_right_subtree_of_y]
           
            From 1 and 2: key[y] is the smallest key in T larger than key[x].

            Similar argument can be given for second case.

12.3.1. 
            public void insert (int value)

     {  

         root = insert ( value, root ); 

     }

    private BSTnode insert ( int value, BSTnode node )
    {
      if ( node == null )
         return new BSTnode(value);
      else if (key[node] > value)
         node.left  = insert ( value, node.left );
      else
         node.right = insert ( value, node.right );
      return node;
    }

12.3.2. Number of nodes examined while searching also includes the node which is searched for, which isn't the case when we inserted it.

12.3.3. Inorder-Tree walk is O(n). So, complexity for sorting by using this method is governed by insertion.

           Worst-case: O(n^2). One example will be when we insert the nodes in sorted order.

          Best-case: O(n log(n)). When we're able to achieve a balanced tree while insertion.

12.3.4. If node 'z' has two child, when the node 'z' is deleted we'll copy the satellite data of it's successor which is node 'y' and replace it's satellite data with it's right child's data. Now, if this happens the data structure pointing to 'y' will point to a node with a completely different satellite data.

          1st Solution:  Update the data structure to point to the new node which contains satellite data of 'y'.

         2nd Solution: Place 'y' into z’s position after deleting z: make right('y') the child of parent('y'); connect 'y' to z’s children and parent.

12.3.5. Example: in fig. 12.4 from the cormen book itself. 
      Deletion : First delete node '10' then, delete node '12'. It'll give a different tree, when we reverse this deletion step.

12.3.6. 
    
12.2.             Radix-Sort(Node n, String s)
                     {
                           if(n->light_shaded)
                                 print s;
                           if(n->left)
                                Radix-Sort(n->left, s+key[n]);
                           if(n->right)
                                Radix-Sort(n->right, s+key[n]);
                     }