Programming Interviews Exposed Java Solutions Chapter 05 - Trees Graphs

Chapter 5 of this book makes it's way quickly into binary search trees and graphs, a great general overview of how they work. 

Many operations in blancened trees are O(log(N)) runtime, here's how that works

• x = num times you can half nodes before getting to 1
• can be expressed as 2^x=n   or...   n = 2^x
• Example:

8 / 2 = 4
4 / 2 = 2
1 / 2 = 1

• In this example it took three times to get to 1, so x = 3
• O(log₂(n))  or just O(log(n))
• Log_bN = x      <-------->     b^x = N
• log base of the num elements equals how many times it will take to get there
• base to the something equals the num of elements or...
• Long story short, if you can half the nodes (and it's balanced), search time is O(log(n))

Many tree problems can be solved recursivly

If Heaps always keep the biggest value on top, then trees are a great way to represent that.  Think patients in a waiting room, heart attack priority 100, cut finger priority 20.  Getting max value is O(1) in a heap.

Finding a node iteratively is a good example of navigating a tree without recursion.

    public Node findNodeIter(Node root, int val) {
        while (root != null) {
            if ( root.data == val ) {
                return root;
            }
            else if ( val < root.data  ) {
                root = root.left;
            }
            else if ( val < root.data ) {
                root = root.right;
            }
            else {
                return root;
            }
        }
        return null;
    }

Searches (finding)

Breadth-First Search: visit all nodes on this level first
Depth-First Search: run down branches and find deepest nodes first

Traversal (visiting)

Basically, when do you visit the node itself, pre visiting children, in order, or post children.

preorder: visit this node, then left descendants, then right
inorder: left descendants first, self, right descendents 
postorder: left descendants, right descendents, then itself

01.  Perform a pre-order traversal on a binary search tree

Ok, recursivly visiting a BST is pretty easy, creating one in Java?  Ugh, creating the tree might even be a better question as it will show how will a candidate knows their Java pointers.  Notice how I always have to reassign head when initializing. Solution

    private void preOrderTraversal(Node head) {
        System.out.println(head.value);

        if (head.left != null) {
            preOrderTraversal(head.left);
        }
        if (head.right != null) {
            preOrderTraversal(head.right);
        }
    }

02.  Perform a pre-order traversal on a binary search tree, without recursion

This one is actually pretty tough, but not so bad if you're familiar with finding a node iteratively.  

    void preorderTraversal( Node root ){
        Stack stack = new Stack<>();

        stack.push( root );
        while( true ){
            Node curr = null;

            try 

            if( curr == null )
                break;

            System.out.println(curr.data);

            Node n = curr.right;
            if( n != null )
                stack.push( n );

            n = curr.left;
            if( n != null )
                stack.push( n );
        }
    }

Output...

       5               
      / \       
     /   \      
    /     \     
   /       \    
   3       8       
  / \     / \   
 /   \   /   \  
 2   4   7   9   
        /       
        6       
                                
5
3
2
4
8
7
6
9

03.  Find the lowest common ancestor of two nodes

First thought was to create two stacks for the parents leading up to each node, then compare them until I don't find a match. However that thinking was way to quick and doesn't take advantage of how a binary tree works.  If the current node is less than or greater than the search value, we move down the hierarchy.  Stop when one is greater or less than. 

    Node lowestCommonParent(Node tree, int a, int b) {
        Node current = tree;
        while ( current != null ) {
            if ( (int) current.data > a && (int) current.data > b ) {
                current = current.left;
            }
            else if ( (int) current.data < a && (int) current.data < b) {
                current = current.right;
            }
            else {
                return current;
            }
        }
        return null;
    }

Output...

       5               
      / \       
     /   \      
    /     \     
   /       \    
   3       8       
  / \     / \   
 /   \   /   \  
 2   4   7   9   
        /       
        6       
                                
Lowest common parent of 9 and 6 is : 8
Lowest common parent of 7 and 6 is : 7