Home › DSA › Trees

easy Binary Tree Paths

Problem Statement

Given the root node of a binary tree, return all unique paths from the root node to the leaf node in any order.

Examples

Example 1:

Input: root = [1,2,3,null,null,4,5]

Expected Output: ["1->2", "1->3->4", "1->3->5"]
Justification: The binary tree has one root-to-leaf path for the left child (1->2) and two for the right child, branching into 4 and 5 respectively.

Example 2:

Input: root = [5,3,6,2,4,null,null,1]

Expected Output: ["5->3->2->1", "5->3->4", "5->6"]
Justification: There are three paths leading to leaf nodes: one through the left subtree down to 1, another through the left subtree to 4, and one path through the right subtree to 6.

Example 3:

Input: root = [2,null,3,null,4,null,5]

Expected Output: ["2->3->4->5"]
Justification: There's only one path from the root to the leaf, cascading down the right children.

Try it yourself

Try solving this question here:

✅ Solution Binary Tree Paths

Problem Statement

Given the root node of a binary tree, return all unique paths from the root node to the leaf node in any order.

Examples

Example 1:

Input: root = [1,2,3,null,null,4,5]

Expected Output: ["1->2", "1->3->4", "1->3->5"]
Justification: The binary tree has one root-to-leaf path for the left child (1->2) and two for the right child, branching into 4 and 5 respectively.

Example 2:

Input: root = [5,3,6,2,4,null,null,1]

Expected Output: ["5->3->2->1", "5->3->4", "5->6"]
Justification: There are three paths leading to leaf nodes: one through the left subtree down to 1, another through the left subtree to 4, and one path through the right subtree to 6.

Example 3:

Input: root = [2,null,3,null,4,null,5]

Expected Output: ["2->3->4->5"]
Justification: There's only one path from the root to the leaf, cascading down the right children.

Solution

To solve this problem, we will employ a depth-first search (DFS) approach. DFS is particularly well-suited for this task because it allows us to explore each branch of the tree to its fullest extent (down to the leaf nodes) before backtracking. This ensures that we can collect all root-to-leaf paths efficiently. The algorithm works by traversing the tree from the root node, appending the value of each visited node to a path string, and recursively exploring all possible paths down to the leaf nodes. Once a leaf node is reached, the current path string is added to a list of paths. This method is applied recursively to each node's left and right children if they exist. By using DFS, we can guarantee that all paths are explored, and the use of recursion simplifies the traversal logic.

Our approach is effective because it aligns with the natural structure of binary trees, allowing us to leverage their hierarchical nature to efficiently navigate and record paths. DFS ensures that no node is missed and that each path is fully recorded before moving on to the next. This strategy is optimal for this problem because it minimizes unnecessary computations and visits each node exactly once, ensuring all unique root-to-leaf paths are captured.

Step-by-Step Algorithm

Start at the Root: Begin the process with the root node of the binary tree.
Initialize Paths List: Create an empty list to store the paths from the root to each leaf.
Recursive Function - findPaths: Define a recursive function that takes the current node, the path so far (as a string), and the paths list as arguments. This function will be used to explore all possible paths from the root to the leaves.
Base Case: In the recursive function, check if the current node is null. If it is, return immediately, as this path cannot lead to a leaf.
Update Path: Append the current node's value to the path string. If the current node is not null, this means we are on a potential path to a leaf.
Leaf Node Check: Check if the current node is a leaf (i.e., both its left and right children are null). If it is, add the current path to the paths list as a complete root-to-leaf path.
Recursive Exploration: If the current node is not a leaf, recursively call the function on both the left and right children of the current node, if they exist. Before making the recursive call, add "->" to the path string to indicate the path's continuation.
Return Paths: After all recursive calls complete, return the paths list containing all root-to-leaf paths found.

Algorithm Walkthrough

Start at Root (5): The path starts with "5".
Move to Left Child (3): The path updates to "5->3". Since 3 is not a leaf, continue down.
Explore Left of 3 (2): Path updates to "5->3->2". 2 is not a leaf; it has a right child.
- Move to Right of 2 (1): Path is "5->3->2->1". 1 is a leaf, so add "5->3->2->1" to paths.
Backtrack to 3 and Go Right (4): Path from 5 is "5->3". Now update path to "5->3->4". 4 is a leaf, so add "5->3->4" to paths.
Backtrack to 5 and Move to Right Child (6): Now explore the right side of 5. The path is "5->6". Since 6 is a leaf, add "5->6" to paths.

Completed Paths:

By following the steps above, the algorithm discovers all paths:
- "5->3->2->1"
- "5->3->4"
- "5->6"

These steps systematically explore each branch of the tree, ensuring that every unique root-to-leaf path is identified and recorded.

Code

java

import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
// public static class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    if (root != null) findPaths(root, "", paths);
    return paths;
  }

  // Helper method to construct paths
  private void findPaths(TreeNode node, String path, List<String> paths) {
    if (node == null) return; // Base case: if the node is null, return

    // Append the current node's value to the path
    path += Integer.toString(node.val);

    // If it's a leaf node, add path to list; otherwise, explore children
    if (node.left == null && node.right == null) paths.add(path);
    else {
      path += "->"; // Add delimiter for the next node
      findPaths(node.left, path, paths); // Recursively find left paths
      findPaths(node.right, path, paths); // Recursively find right paths
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    TreeNode root2 = new TreeNode(5);
    root2.left = new TreeNode(3);
    root2.right = new TreeNode(6);
    root2.left.left = new TreeNode(2);
    root2.left.right = new TreeNode(4);
    root2.left.left.left = new TreeNode(1);
    System.out.println("Example 2: " + sol.binaryTreePaths(root2));

    TreeNode root3 = new TreeNode(2);
    root3.right = new TreeNode(3);
    root3.right.right = new TreeNode(4);
    root3.right.right.right = new TreeNode(5);
    System.out.println("Example 3: " + sol.binaryTreePaths(root3));
  }
}

Complexity Analysis

Time Complexity:

: Where N is the number of nodes in the binary tree. In the worst case, we visit each node exactly once to either extend the path string or to backtrack.

Space Complexity:

: In the worst-case scenario, the space complexity is determined by the height of the binary tree, which influences the recursion stack depth. For a skewed binary tree (one where every parent node has only one child), the height of the tree can be N, leading to a space complexity of .

🤖 Don't fully get this? Learn it with Claude

Stuck on Binary Tree Paths? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Binary Tree Paths** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Binary Tree Paths** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Binary Tree Paths**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Binary Tree Paths**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Binary Tree Path Sum Sum of Root To Leaf Binary Numbers →