Binary Tree Paths

Problem Statement

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

[“1->2->5”, “1->3”]

Approach

• If the root is null, return empty list
• If root.left and root.right are null, then return root in a String
• If root.left is null then recursively traverse path of the right subtree until the leaf
• If root.right is null then recursively traverse path of the left subtree until the leaf
• If root.left and root.right both are not null
• Recursively traverse the left and right subtrees
• One thing to notice is since we are creating the paths using a String. Each recursive call requires a new String concatenated with the existing path already discovered.

Run Time Complexity

The time complexity for this problem is O(n). In the worst case we shall be visiting all the nodes of the tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    List<String> list = new ArrayList<String>();
    
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return list;
        }
        addToPath(root, "");
        return list;
    }
    
    
    private void addToPath(TreeNode node, String s){
       
        if(node.left == null && node.right == null){
            list.add(s+node.val);
            return;
        }
        if(node.left == null){
            addToPath(node.right, ""+s+node.val+"->");
            return;
        }
       if(node.right == null){
            addToPath(node.left, ""+s+node.val+"->");
            return;
        }
         addToPath(node.left, ""+s+node.val+"->"); 
         addToPath(node.right, ""+s+node.val+"->");
    }
}