Binary Tree Paths

Problem Statement

In this challenge, we are given the root node of a binary tree and are required to produce a list of all paths from the root to each leaf node. A path needs to represent the sequence of values from the root down to a leaf, where a leaf is defined as a node without any children. The paths should be written as a series of node values concatenated by "->". The function should be able to handle varying sizes and shapes of binary trees and can return the list of paths in any order.

Examples

Example 1

Input:

root = [1,2,3,null,5]

Output:

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

Example 2

Input:

root = [1]

Output:

["1"]

Constraints

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

Approach and Intuition

Understanding the problem through the examples given:

1. Example 1:

   • Input: The tree structure is [1,2,3,null,5] which represents a binary tree where the root node 1 has two children, 2 and 3. Node 2 itself has a right child, 5, and 3 is a leaf node.
   • Output: The solution outputs two paths: "1->2->5" and "1->3". The path "1->2->5" describes the path from the root (1) to the leaf (5) via node 2, and "1->3" directly from root (1) to leaf (3).

2. Example 2:

   • Input: The tree structure is [1], which is simply a single node that is a root as well as a leaf.
   • Output: The only path in the output is "1", which directly represents the root/leaf node.

The constraints provide us with important limits:

• The tree can contain between 1 and 100 nodes.
• Node values range between -100 and 100.

Given this, a straightforward approach to solving this problem would be to use a depth-first search (DFS). DFS is ideal here due to its nature of exploring as far as possible along a branch before backtracking, perfectly aligning with the requirement to explore from root to leaf. Here’s the strategy:

1. Start at the root and initiate a path string with the root's value.
2. Traverse the tree by going all the way down to the left and then to the right (If any) while appending the current node value to the path string.
3. Whenever a leaf node is hit (both left and right children are null), store the current path string in the result list.
4. Backtrack and remove the current node value from the path string, then proceed to explore remaining paths.

By following this method, the algorithm ensures all paths are properly discovered and recorded.

Solutions

class Solution {
  public List<String> getAllPaths(TreeNode root) {
    LinkedList<String> allPaths = new LinkedList();
    if (root == null)
      return allPaths;

    LinkedList<TreeNode> nodes = new LinkedList();
    LinkedList<String> paths = new LinkedList();
    nodes.add(root);
    paths.add(Integer.toString(root.val));
    TreeNode currentNode;
    String currentPath;

    while (!nodes.isEmpty()) {
      currentNode = nodes.pollLast();
      currentPath = paths.pollLast();
      if (currentNode.left == null && currentNode.right == null)
        allPaths.add(currentPath);
      if (currentNode.left != null) {
        nodes.add(currentNode.left);
        paths.add(currentPath + "->" + Integer.toString(currentNode.left.val));
      }
      if (currentNode.right != null) {
        nodes.add(currentNode.right);
        paths.add(currentPath + "->" + Integer.toString(currentNode.right.val));
      }
    }
    return allPaths;
  }
}