Tree related questions

1. 
   Question:Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. QuestionLink
   
   
   Answer: bottom up approach: build subtree first up to the root analysis from LeetCodeDiscussion In the previous array to BST, we construct the BST in a top-down way.
   For the list data structure, to get the mid point every time is a waster of time. So construct the BST in a bottom-up way. However, the length of the list must be computed.
   Recursively
   
   1. construct the left tree
   2. construct the root node, list pointer +1.
   3. construct the right node
   
   

   public ListNode list = null; //use class variable to address Java only pass parameter by references
       public TreeNode sortedListToBST(ListNode head) {
           if(head==null) return null;
           list = head;
           ListNode curr= head;
           int length=0;
           while(curr!=null) {
               curr=curr.next;
               length++;
           }
           return sortedListToBSTHelper(0, length-1);
       }
       public TreeNode sortedListToBSTHelper(int start, int end) {
           if(start>end) return null;
           int mid = (start+end)/2;
           TreeNode left = sortedListToBSTHelper(start, mid-1);
           TreeNode parent = new TreeNode(list.val);
           list=list.next;
           TreeNode right = sortedListToBSTHelper( mid+1, end);
           parent.left = left;
           parent.right = right;
           return parent;
       }
   

2. 
   Question:Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.QuestionLink
   
   
   Answer: just to remember to remove the tailing node saved in the path after finishing recursion
   
   

   public ArrayList< ArrayList<Integer> > pathSum(TreeNode root, int sum) {
           ArrayList< ArrayList<Integer> > result = new ArrayList< ArrayList<Integer> >();
           ArrayList<integer> path = new ArrayList<integer>();
           pathSumHelper(root,sum, path, result);
           return result;
    }
       
    public void pathSumHelper(TreeNode root, int sum, ArrayList<integer> path, ArrayList< ArrayList<Integer> > result) {
           if (root==null) return;
           path.add(root.val);
           if (root.left==null&&root.right==null&&root.val==sum) {
               ArrayList<integer> onePath = new ArrayList<integer>(path); //have to make a copy of path
               result.add(onePath);
           } else {
               pathSumHelper(root.left, sum-root.val, path, result);
               pathSumHelper(root.right, sum-root.val, path, result);
           }
           path.remove(path.size()-1);
    }
   

   
   Question:Implement In-order/Pre-Order/Post-Order Iterator for Binary Tree QuestionLink
   
   Interface looks like:
   

   public interface InOrderBinaryTreeIterator extends Iterator { 
     /** Returns the next integer a in the in-order traversal of the given binary tree.
      *  For example, given a binary tree below,
      *       4
      *      / \
      *     2   6
      *    / \ / \
      *   1  3 5  7
      * the outputs will be 1, 2, 3, 4, 5, 6, 7. 
      */ 
     public Integer next(); 
   
     /** Return true if traversal has not finished; otherwise, return false.
      */ 
     public boolean hasNext();
   }
   

   
   Answer: Iterator means we can NOT save all tree nodes into a container and then iterating through the container.
   
   idea like:
   1) Find the left-most node of the root and store previous left children in a stack;
   2) Pop up the top node from the stack;
   3) If it has a right child, find the left-most node of the right child and store left children in the stack.
   
   
   

   //InOrder (LNR) iterator key: when initialize the stack, push root and all its left child into the stack; 
   public class InOrderBinaryTreeIteratorImpl implements InOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Push node cur and all of its left children into stack */  
      private void pushLeftChildren(TreeNode cur) {  
        while (cur != null) {  
          stack.push(cur);  
          cur = cur.left;  
        }  
      }  
      
      /** Constructor */  
      public InOrderBinaryTreeIterator(TreeNode root) {  
        pushLeftChildren(root);  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop();  
        pushLeftChildren(res.right);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   //PreOrder (NLR) iterator key: only push root into Stack in Constructor; push right and then left into Stack in Next function
    public class PreOrderBinaryTreeIteratorImpl implements PreOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Constructor */  
      public PreOrderBinaryTreeIterator(TreeNode root) {  
        if (root != null) {  
          stack.push(root); // add to end of queue 
        }  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop(); // retrieve and remove the head of queue 
        if (res.right != null) stack.push(res.right);  
        if (res.left != null) stack.push(res.left);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   //PreOrder (NLR) iterator key: only push root into Stack in Constructor; push right and then left into Stack in Next function
    public class PreOrderBinaryTreeIteratorImpl implements PreOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Constructor */  
      public PreOrderBinaryTreeIterator(TreeNode root) {  
        if (root != null) {  
          stack.push(root); // add to end of queue 
        }  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop(); // retrieve and remove the head of queue 
        if (res.right != null) stack.push(res.right);  
        if (res.left != null) stack.push(res.left);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }    
   
   public class PostOrderBinaryTreeIteratorImpl implements PostOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** find the first leaf in a tree rooted at cur and store intermediate nodes */  
      private void findNextLeaf(TreeNode cur) {  
        while (cur != null) {  
          stack.push(cur);  
          if (cur.left != null) {  
            cur = cur.left;  
          } else {  
            cur = cur.right;  
          }  
        }  
      }  
      
      /** Constructor */  
      public PostOrderBinaryTreeIterator(TreeNode root) {  
        findNextLeaf(root);  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop();  
        if (!stack.isEmpty()) {  
          TreeNode top = stack.peek();  
          if (res == top.left) {  
            findNextLeaf(top.right); // find next leaf in right sub-tree 
          }  
        }  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   public ArrayList<Integer> postorderTraversal(TreeNode root) {  
      PostOrderBinaryTreeIterator iterator = new PostOrderBinaryTreeIteratorImpl(root);  
      ArrayList<Integer> results = new ArrayList<Integer>();  
      while (iterator.hasNext()) {  
        results.add(iterator.next());  
      }  
      return results;  
    }