[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.7] T2 is a subtree of T1

1. Example



10 million nodes = 10*10^6 = 10 ^7
int 32 bit = 4 byte
4B * 10^7 = 40 MB



2. Implementation

// Approach #1  Memory is not an issue

T1 String traversal = a string s1 O(10^6)
T2 String traversal = a string s2 O(100)
s2 is a substring of s1 if preorder traversal and inorder traversal both apply

substring : check using a suffix tree
suffix tree of 10^6 length string ==> char 2 byte [26]
2B*26*10^6 = 52MB

26*26*26......
suffix tree is memory intensive

A1: b i  b s

s
ibs
b s
    ibs
                         root
            /              |         \
           B   0,2     I   1      S 3
         /    \           |       
       I0      S2     B  1
       |                   |
       B0               S 1
       |
       S0

// Approach #2 Memory is an issue and we try this approach
// Worst case :Time O(n*m), where n and m is the sizes of trees T1 and T2, respectively
// Avg Case   :Time O(k*m + n)
// If k is the occcurrences of T2'root in T1, the worst case runtime can be characterized as O(k*m + n)

boolean containsTree(TreeNode t1, TreeNode t2)
{


      // validate the input
      if  ( t2 == null )
          return true;



      
      return subTree( t1, t2);




}
// Find the root with the same value
boolean sunTree(TreeNode r1, TreeNode r2)
{ 



      // Base case
      if ( r1 == null) // till the leaf and cannot find the subtree
         return false;
      

      
      if (r1.val === r2.val)
      {
          if (  matchTree(r1, r2)  )
             return true;    
      }



      return subTree(r1.left, r2) || subTree(r1.right, r2);
 

}

boolean matchTree(TreeNode r1, TreeNode r2)
{
      

      if (r1 == null && r2 == null)
          return true;
      if ( r1 == null || r2 == null )
          reutrn false;
      if (r1.val != r2.val)
          return false;

    
      return matchTree( r1.left, r2.left ) && matchTree(r1.right, r2.right);
    
}

3. Similar ones

[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

[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;

}

OR

    //while(lastHead!=null)  

    //{  

       // TreeLinkNode lastCur = lastHead;  

        while(lastCur != null)  

        { 

            .....

            if (lastCur == null)

            {

                  lastCur = curHead;  

                  curHead = null;

            }

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

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/

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

[4.1] Balanced Tree ?

1.Example

A balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root
by more than one.

The idea is the difference of min depth and max depth should not exceed 1.


http://www.stoimen.com/blog/2012/06/22/computer-algorithms-binary-search-tree-data-structure/


2. Implementation

private static int maxDepth(TreeNode root)
{
     // Base case
     if(root == null)
        return 0;
     return 1 + Math.max( maxDepth(root.left), maxDepth(root.right) );
}
private static int minDepth(TreeNode root)
{
     // Base case 
     if (root == null)
       return 0;
     return 1 + Math.max( minDepth(root.left), minDepth(root.right) );
}
public static boolean isBalanced(TreeNode root)
{
    return ( (maxDepth(root) - minDepth(root) ) <=1 );
}

3. Similar Ones