Root to leaf paths

Problem

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

Note: A leaf is a node with no children.

Example:

Input:

   1

 /   \

2     3

 \

  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution

We can pre-order traversal the tree, use an array to record the path, once reach the leaf, print out the path. Since we want to print out all the path instead of just one, we need to backtrack. After visiting a subtree, the root node of the subtree needs to be removed from the array.

The time cost will be O(N) since we need to visit each node, the space cost will be proportional to the height of the tree. So space cost is O(logN) to O(N).

import java.util.*;
public class RootToLeaf {
  /*
   1
 /   \
2     3
 \
  5

  */
  public static void rootToLeaf(Node root, List<Integer> path) {//1
    if(root == null) return;
    if(root.left == null && root.right == null) {
      path.forEach(i -> System.out.print(i + "->"));//1->2->5, 1->3
      System.out.println(root.value);
      return;
    }
    path.add(root.value);//""
    rootToLeaf(root.left, path);
    rootToLeaf(root.right, path);
    path.remove(new Integer(root.value));
  }

  public static void main(String...args) {
    Node root = new Node(1, new Node(2, null, new Node(5, null, null)), new Node(3, null, null));
    List<Integer> path = new ArrayList<>();
    rootToLeaf(root, path);
  }

  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time cost O(N), space cost O(H).