Thursday, November 6, 2014

Facebook: Print all the paths from root to every leaf in a binary tree

Print all the paths from root to every leaf in a binary tree

Recursive Solution:
public class Solution {
    public List<List<Integer>> printPath(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        printPathHelper(root, curr, result);
        
        return result;
    }
    
    private void printPathHelper(TreeNode root, List<Integer> curr, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        
        curr.add(root.val);
        
        if (root.left == null && root.right == null) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (root.left != null) {
          printPathHelper(root.left, curr, result);
          curr.remove(curr.size() - 1);
        }   
        
        if (root.right != null) {
          printPathHelper(root.right, curr, result);
          curr.remove(curr.size() - 1);
        }
    }
 }

Take-away message:
Note that we must check root.left and root.right before we go to the root's children. That is because we need to delete the node after we traverse it. For e.g. 
   1
     \
       3
If we don't check that, the node 1 will be deleted.

Another Solution just print the path:
public void printPaths() { 
  int[] path = new int[1000]; 
  printPaths(root, path, 0); 
}

private void printPaths(Node node, int[] path, int pathLen) { 
  if (node==null) return;

  // append this node to the path array 
  path[pathLen] = node.data; 
  pathLen++;

  // it's a leaf, so print the path that led to here 
  if (node.left==null && node.right==null) { 
    printArray(path, pathLen); 
  } 
  else { 
  // otherwise try both subtrees 
    printPaths(node.left, path, pathLen); 
    printPaths(node.right, path, pathLen); 
  } 
}

Iterative Solution:
public class Solution {
    public void printPath(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> levelStack = new Stack<Integer>();
        
        int[] path = new int[1000];
        
        nodeStack.push(root);
        levelStack.push(0);
        
        while (!nodeStack.isEmpty()) {
            TreeNode curr = nodeStack.pop();
            int level = levelStack.pop();
            
            path[level] = curr.val;
            
            if (curr.left == null && curr.right == null) {
                printCurrPath(path, level + 1);
                continue;
            }
            
            if (curr.right != null) {
                nodeStack.push(curr.right);
                levelStack.push(level + 1);
            }
            if (curr.left != null) {
                nodeStack.push(curr.left);
                levelStack.push(level + 1);
            }
        }
    }
}

No comments:

Post a Comment