Binary Tree Paths

EASY

Description

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

A leaf is a node with no children.

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

Approaches

Checkout 3 different approaches to solve Binary Tree Paths. Click on different approaches to view the approach and algorithm in detail.

Recursive DFS with String Building

Use recursive depth-first search (DFS) to traverse the binary tree and build paths as strings during traversal. At each node, append the current node's value to the path and use string concatenation.

Algorithm

Initialize an empty list to store all paths
If root is null, return empty list
Call DFS helper function with initial empty path
In DFS helper:
- Append current node value to path
- If current node is leaf, add path to result list
- Recursively call DFS on left and right children if they exist

This approach uses recursive DFS to traverse the binary tree from root to leaf. At each node, we append the current node's value to the current path string. When we reach a leaf node (node with no children), we add the complete path to our result list.

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        dfs(root, "", paths);
        return paths;
    }
    
    private void dfs(TreeNode node, String path, List<String> paths) {
        // Build current path
        path += (path.isEmpty() ? "" : "->") + node.val;
        
        // If leaf node, add path to result
        if (node.left == null && node.right == null) {
            paths.add(path);
            return;
        }
        
        // Recurse on children
        if (node.left != null) dfs(node.left, path, paths);
        if (node.right != null) dfs(node.right, path, paths);
    }
}

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the tree. Each node is visited exactly once.Space Complexity: O(N) for storing the paths. In worst case (skewed tree), the recursion stack can go up to O(N)

Pros and Cons

Pros:

Simple and intuitive implementation
Easy to understand and maintain
Works directly with string representation

Cons:

Creates new string objects at each recursive call
String concatenation is inefficient
Higher memory usage due to string immutability

Code Solutions

Checking out 3 solutions in different languages for Binary Tree Paths. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < String > ans = new ArrayList <>(); private List < String > t = new ArrayList <>(); public List < String > binaryTreePaths ( TreeNode root ) { dfs ( root ); return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } t . add ( root . val + "" ); if ( root . left == null && root . right == null ) { ans . add ( String . join ( "->" , t )); } else { dfs ( root . left ); dfs ( root . right ); } t . remove ( t . size () - 1 ); } }

Video Solution

Watch the video walkthrough for Binary Tree Paths

Algorithms:

Depth-First Search

Patterns:

Backtracking

Data Structures:

StringTreeBinary Tree

Companies:

Google |Capital One |Revolut |