Problem 13 - Binary Tree Paths

Explore our archive for previous posts.

Question

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

Approach

In this solution, we perform a depth-first search (DFS) traversal of the binary tree. We maintain a path variable to keep track of the current path from the root to the current node. Whenever we reach a leaf node, we append the leaf node's value to the path and add it to the paths list. We recursively call the DFS function on the left and right children of each node, updating the path accordingly.

The binaryTreePaths function initializes the paths list and checks for the base case of an empty tree. Then, it calls the dfs function to perform the DFS traversal and populate the paths list. Finally, it returns the list of binary tree paths.

Solution

Solve it here

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>(); 
        
        if (root != null) {
            dfs(root, "", paths); // Start the depth-first search with an empty path
        }
        
        return paths;
    }
    
    private void dfs(TreeNode node, String path, List<String> paths) {
        // Base case: If the current node is a leaf node
        if (node.left == null && node.right == null) {
            paths.add(path + node.val); // Add complete path to the list
            return;
        }
        
        // Recurse on the left child if it exists
        if (node.left != null) {
            dfs(node.left, path + node.val + "->", paths);
        }
        
        // Recurse on the right child if it exists
        if (node.right != null) {
            dfs(node.right, path + node.val + "->", paths);
        }
    }
}

Time and space complexity

Time Complexity: This solution has a time complexity of O(n), where n is the number of nodes in the binary tree. This is because we visit each node once during the DFS traversal.

Space Complexity: The space complexity is O(h), where h is the height of the binary tree. This is because the space used by the recursive call stack depends on the height of the tree. In the worst case, where the binary tree is skewed and has a height of n (essentially becoming a linked list), the space complexity would be O(n).