Cracking the coding interview Tree and Graphs

Monday, October 12, 2015

[4.8] any path sum

1. Example

All Path and find out which path has a sum,

http://algorithms.tutorialhorizon.com/files/2014/11/Maximum-Sum-path-between-two-leaves.png

-5->4 ->11 -2 -8 7 12==> sum(20) -12-7+8+2-11 = 0

helper(root, List<Integer> )
list.add(root.val)
//** check every path so far, are they a sum, by minus all the previous node to check

we look “up” to see if we’ve found the sum.“does this node complete a path with the sum?”

helper(root.left, new List<Integer>(list) )
helper(root.right, new List<Integer>(list) )

http://codercareer.blogspot.com/2011/09/no-04-paths-with-specified-sum-in.html

Figure 1: A binary tree with two paths where the sum of all nodes value is 22:

One is the path contains node 10 and 12,

and the other contains node 10, 5 and 7

2. Implementation


// Time:O(n log n)
// 2^r nodes at level r
// ever level every node

// n node, and for each node loop up take O(logn)

void findSum(TreeNode root, int sum, List list, int start)
{


        // Base case
        if ( root ==null )
            return;
        int tmp = sum;



        list.add(root.val);




        
        for (int stop = start; stop >=0; stop--)
        {
             tmp = list.get(i);
             if (tmp == 0)
                 print(list, start, stop);
        }


        findSum(root.left, sum, new List(list), start+1);
        findSum(root.right, sum, new List(list), start+1);

}

void print(Lsit lsit, int start, int stop)
{
      for (int i = start; i <= stop;i++)
      {
               System.out.print(list.get(i)+" ");
      }
      System.out.println();
}

3. Similar ones
http://karmaandcoding.blogspot.com/2012/11/binary-search-tree-any-path-sum.html

[4.6] Frist(Lowest) Commonacestor

1. Example

1. Not a binary search tree,
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1
Time complexity of the above solution is O(n)Attempt#1
Attempt#2
http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

the LCA of nodes 5and 1 is 3.
Please note that LCA for nodes 5 and 4 is 5.
Please note that LCA for nodes 7 and 4 is 2. (although 5,3 are also ancestors, but not the lowest)

2. binary search tree, we could do a modified find on the two nodes and see where the paths diverge.

http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Time complexity is O(h) where h is height of tree
Recursive, Iterativehttp://algorithms.tutorialhorizon.com/files/2014/11/LCA-in-Binary-Search-Tree.png

2. Implementation

// LCA for Binary Tree

// Time:O(n)
// 1. Recursive #1
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{


     if ( isChild(root.left, p1) && isChild(root.right, p2) )
           return LCA(root.left, p1 ,p2);
     if ( isChild(root.right,p1) && isChild(root.right,p2) )
           return LCA(root.right, p1,p2);
     return root;
   

}
private boolean isChild(TreeNode root, TreeNode p)
{
     if (root == null)
          return false;
     if (root == p)
          return true;
     return isChild(root.left, p) || isChild(root.right, p);
}


// 2. Recursive #2

// Case1: If there are two nodes on one of the sides, then we have
// to check if the child node on this side is p or q (because in this 
// case the current node is the common ancestor).
// If the child node is neither p nor q, we should continue to search 
// further (starting from the child).

// Case2:  If one of the searched nodes (p or q) is located on the right 
// side of the current node, then the other node is located on the other 
// side. Thus the current node is the common ancestor

public class Solution
{


      static int TWO_NODES_FOUND = 2;
      static int ONE_NODE_FOUND = 1;
      static int NO_NODE_FOUND = 0;
   




      public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
      {

             // Same node and only node node below
             if ( p2 == p1 && (root.left == p2 || root.right == p1) )
                 return root;


             int nodesFromLeft =  isChild(root.left, p1,p2);
             if (  nodesFromLeft == TWO_NODES_FOUND ) 
             {
                     if (root.left == p1 || root.left == p2)
                         return root.left;
                     else 
                         return LCA(root.left, p1,p2);
             }
             else if (  nodesFromLeft == ONE_NODE_FOUND   ) 
             {
                     if (root == p) return p;
                     else if (root == q) return q;
             }

             int nodeFromRight = isChild(root.right, p1, p2);
            if (  nodeFromRight == TWO_NODES_FOUND ) 
             {
                     if (root.right == p1 || root.right == p2)
                         return root.left;
                     else 
                         return LCA(root.right, p1,p2);
             }
             else if (  nodeFromRight == ONE_NODE_FOUND   ) 
             {
                     if (root == p) return p;
                     else if (root == q) return q;
             }




             if (  nodeFromLeft == ONE_NODE_FOUND && nodeFromRight == ONE_NODE_FOUND  )
                  return root;
             else 
                  return null;


      }






      // Check how many nodes (p1, p2 ,p1 and p2, none) under this root
      // Output: 0(NO_NODES_FOUND),1(ONE_NODE_FOUND),2(TWO_NODES_FOUND)
      private int isChild(TreeNode root, TreeNode p1, TreeNode p2)
      {


/*
             int ret= NO_NODES_FOUND;
           


             if (root==null)
                   return NO_NODES_FOUND;
             if (root == p1 || root == p2)
                   ret+=1;


             // isChild(root.left..) || isChild(root.right,..)
             ret += isChild(root.left, p1,p2);
             if ( ret = TWO_NODES_FOUND )   //FOUND p1 and p2
             {
                 return ret;
             }
             return ret + isChild(root.right, p1, p2);
*/

             int ret = 0;
             ret += isChild(root, p1)?1:0;
             ret += isChild(root, p2)?1:0;
             return ret;
                  

      }


      private boolean isChild(TreeNode root, TreeNode p)
      {
          if (root == null)
              return false;
          if (root == p)
              return true;
          return isChild(root.left, p) || isChild(root.right, p);
      }
}

// LCA for Binary Search Tree

// Time :O(logn) = O(h), h is the height of the tree
// 1. Recursive Space:O(n)
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{


     // Base case
     if ( root == null )
         return null;
  

     if ( root.val > p1.val && root.val > p2.val ) 
           return LCA( root.left, p1, p2 );
     else if ( root.val < p1.val && root.val < p2.val )
           return LCA( root.right, p1, p2); 
     return root;


}
// 2. Iterative Space:O(1)
public TreeNode LCA(TreeNode root, TreeNode p1, TreeNode p2)
{
      while ( root != null )
      {
           if ( root.val > p1.val && root.val > p2.val  ) 
              root = root.left;
           else if (  root.val < p1.val && root.val < p2.val  )
              root = root.right;
           else 
              break;
      }


      return root;

}

3. similar Ones

Friday, October 9, 2015

[4.5] Inorder Successor in Binary Search Tree

1. Example
http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/

In the above diagram,
Case1: Has right child, go anyway: inorder successor of 8 is 10,
Case2: No right child and itself is left child : inorder successor of 10 is 12
Case3: No right child and itself is right child: inorder successor of 14 is 20.
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

2. Implementation

public static TreeNode inorderSuccessor(TreeNode e)
{
        


       // valdiate the input
       if ( e == null )
           return null;


   
 
       TreeNode succ;



       // Case 1: Has right child
       if ( e.parent == null || e.right != null )
       {
            succ = leftMostChild(e.right);
       }
       // Case 2,3: No right child
       else
       {
            // case 
            while(   (succ = e.parent) != null )
            {
                 // Case2: No right child and itself is left child
                 if ( succ.left == e)
                     break;
                 // Case3: No right child and itself is right child 
                 e = succ;
            }
       } 



       return succ;

  
}
public static TreeNode leftMostChild(TreeNode e)
{


      // vlaidate the input
      if ( e == null)
        return null;


      // while(e!= null) // NOTE: STOP at e == null, not we want
      while ( e.left!= null ) // NOTE: STOP at e.left == null 
         e = e.left;


      return e;

}

3. Similar Ones

[4.4] Create a linked list of all nodes at each depth

1. Example

Level=> level order traversal => Breath First Search

Method1: list = new LinkedList();

Method2: TreeLinkNode head = root; // use TreeLinkNode next feature as a queue

if ( curHead == null )
{
curHead= lastCur.left;
pre = curHead; }
else
{
pre.next = lastCur.left or ritght
}
// NOTE : the reason need two layer of while is because we no idea
when to update lastHead even we have curHead complete
while (lastHead != null) {

TreeLinkNode lastCur = lastHead; // Like while (!queue.isEmpty())

while ( lastCur != null ) // like for loop in the above {

lastCur = lastCur.next;

}

lastHead = curHead;

curHead = null;

}

//while(lastHead!=null)

//{

// TreeLinkNode lastCur = lastHead;

while(lastCur != null)

{

.....

if (lastCur == null)

{

lastCur = curHead;

curHead = null;

}

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

NOTE: At leaves, for loop all leaves but doesn't add any nodes
list = new LinkedList();

for ( int i = 0 ; i < result.get(level).size();i++ ) { // Like a queue in-insertion order

TreeNode n = (TreeNode) result.get(level).get(i);

if ( n ! = null ) {
if (n.left != null)

list.add(n.left);

if (n.right != null)

list.add(n.right);

}
if (list.size() > 0 ) {

result.add(level+1, list);

}

else {

break;

}

level++;

2. Implementation
In a usual BST, we simply traverse the nodes without caring which level we are on. In this case, it is critical to know the level.
We thus use a dummy node to indicate when we have finished one level and are starting on the next.

public List> findLevelLinkedList(  TreeNode root ) 
{


       int level = 0;
       List> res = new ArrayList>();
       LinkedList list = new LinkedList();
       queue.add(root);
       res.add(level, list);


       
       while(true)
       {



             // NOTE: a new linked list start with a new level
             list = new LinkedList();
             for ( int i = 0 ; i < result.get(level).size();i++ )
             {
                  TreeNode cur = (TreeNode) result.get(level).get(i);
                  if ( cur ! = null )
                  {
                        if (cur.left != null)
                           list.add(cur.left);
                        if (cur.right != null)
                           list.add(cur.right);
                  }
             }



             if (list.size() > 0 )
             {
                   result.add(level+1, list);
             } 
             else
             {
                   break;
             }



             level++;




       }
 

   

       return result;
 


}

struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
}    
public void findLevelLinkedList (TreeNode root)
{



      // vlaidate hte input
      if (root == null)
          return;


      
      TreeLinkNode lastHead = root;   // As a queue
      TreeLinkNode pre = null;
      TreeLinkNode curHead = null;
      //int lastNum = 1;
      //int curNum = 0;
        


      while (lastHead != null)
      {
           TreeLinkNode lastCur = lastHead;
           // Like while (!queue.isEmpty())
           while ( lastCur != null ) // like for loop in the baove
           {
                  if (lastCur.left != null)
                  {
                       if (  curHead == null )
                       {
                             curHead= lastCur.left;
                             pre = curHead;
                       }
                       else 
                       {
                             pre.next = lastCur.left;
                             pre = pre.next;
                       }
                  }
                  if (lastCur.right != null ) 
                  {
                       if (   curHead == null )
                       {
                              curHead = lastCur.right;
                              pre = curHEad;
                       }
                       else 
                       { 
                              pre.next = lastCur.next;
                              pre = pre.next;
                       }
                  }


                  lastCur = lastCur.next;// next element in Queue
                  
           }


           lastHEad = curHead; // new linkedl list in current level
           curHead = null;

      }
       
}

3. similar Ones

[4.3] Sorted array to binary tree

1. Example

12"3"456
/ \
/ \
"1"2 4"5"6
X "2" "4" "6"
X X X X X X

create a binary tree with minimal height = > balanced

The idea is that mid as a root

NOTE: sorted array => array[mid]
SET ROOT FIRST then root left root right
TreeNode root = new TreeNode(array[mid]);

root.left = addTotree(array, start,mid-1);

root.right = addToTree(array, mid+1, end);

return root;

NOTE: sorted linkedlist => linklist[mid] X=> traverse to the first node
SET ROOT left first then root then root.right TreeNode left = helper(list ,start, mid-1);
TreeNode root = new TreeNode(list.get(0).val);// head val

root.left = left;

list.set( 0, list.get(0).next );

root.right = helper( list, m+1, r );

return root;

idx 012345
123456
mid=2
0,2-1
mid = 0
0, -1 X
1,1
mid =1
1,0X
2,1X
root =2
root =1 root.left = X root.right = 2
2+1, 5
mid = 4
3,3
mid = 3
root = 4
5,5
mid =5
root =6
root = 5 root.left =4 root.right =6
root =3 root.left = 1..... root.right = 5

http://algorithms.tutorialhorizon.com/sorted-array-to-binary-search-tree-of-minimal-height/
Sorrted Array To BST Example

http://msoe.us/taylor/tutorial/cs2852/bst
http://algorithms.tutorialhorizon.com/given-a-sorted-singly-linked-list-array-convert-it-into-a-balanced-binary-search-tree/

2. Implementation

public static TreeNode createMinimalBST(int[] array)
{



       if (array == null || array.elgnth == 0)
          return null;



       return addToTree(array, 0, array.length-1);



}


private static TreeNode addToTree(int[] array, int start, int end)
{



       if (start > end)
          return null;



       
       int mid = (start+end)/2;
       TreeNode root = new TreeNode(array[mid]);
       root.left = addTotree(array, start,mid-1);
       root.right = addToTree(array, mid+1, end);
       return root;




}

//public static TreeNode createMinimalBST(int[] array)
public static TreeNode createMinimalBST(ListNode head)
{




       //if (array == null || array.elgnth == 0)
       if (head == null)
          return null;



 
       // NOTE: count to know the length
       ListNode cur = head;
       int length = 0;
       while ( cur != null)
       {
              cur = cur.next;
              length++;
       }





       List list  = new ArrayList();
       list.add(head);





       //return addToTree(array, 0, array.length-1);
       return addToTree(list,0,length-1);




}


private static TreeNode addToTree(int[] array, int start, int end)
{




       if (start > end)
          return null;



       
       int mid = (start+end)/2;
 



       //TreeNode root = new TreeNode(array[mid]);
       //root.left = addTotree(array, start,mid-1);
       //root.right = addToTree(array, mid+1, end); 



   
       TreeNode left = helper(list ,start, mid-1);// first node left is null
       TreeNode root = new TreeNode(list.get(0).val); // first node = head val
       root.left = left;
       list.set( 0, list.get(0).next );
       root.right = addToTree(list, m+1,r);





       return root;




}

3. Similar Ones

[4.2] Find route(Path) between two nodes

1. Example

Depth First Search

2. Implementation

LinkedList stack = new LinkedList();

for (Node u: g.getNodes())

u.state = State.Unvisited;

start.state = State.Visiting;
stack.add(start);

while ( !stack.isEmpty() ) {
Node curr = stack.removeFirst();// pop()

if ( curr!= null ) {

for ( Node v: curr.getAdjacent() ) {
if (v.state == State.Unvisited) {

// NOTE :find sth

if ( v == end)

return true;

else {

v.state = State.Visiting;

stack.add(v);

}

curr.state = State.Visited;
}

}

return false;

public enum State{
    Unvisited, Visited, Visiting;
}


public static boolean FindRoute(Graph g, Node start, Node end)
{



    // Validate the input
    if ( g == null || start == null || end == null )
         return false;



    LinkedList stack = new LinkedList();
    for (Node u: g.getNodes())
        u.state = State.Unvisited;




    start.state = Visting;
    stack.add(start);
    while ( !stack.isEmpty() )
    {




         Node curr = stack.removeFirst();// pop()
         if ( curr!= null )
         {
 




              for ( Node v: curr.getAdjacent() )
              {
                   if (v.state == State.Unvisited)
                   {
                         // NOTE :find sth
                         if ( v == end)
                                return true;
                         else
                         {
                                v.state = State.Visiting;
                                stack.add(v);
                         }
                        
                   }
              }





              curr.state = State.Visited;
         }
    }



    return false;



}

3. Similar One

Monday, October 12, 2015

[4.8] any path sum

[4.7] T2 is a subtree of T1

[4.6] Frist(Lowest) Commonacestor

Friday, October 9, 2015

[4.5] Inorder Successor in Binary Search Tree

[4.4] Create a linked list of all nodes at each depth

[4.3] Sorted array to binary tree

[4.2] Find route(Path) between two nodes