Binary Tree Paths

LeetCode 257: Binary Tree Paths Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a Depth-First Search (DFS) strategy, specifically recursive preorder traversal, to construct path strings incrementally as the algorithm navigates from the root down to each leaf node.

The "Binary Tree Paths" problem requires us to generate a list of all distinct paths from the root of a binary tree to its leaves. A path is defined as a sequence of nodes starting at the root and ending at a node with no children, connected by arrows (e.g., "1->2->5"). This is a fundamental tree traversal challenge that tests your ability to maintain state (the current path) while navigating the tree structure.

This LeetCode 257 solution focuses on constructing these strings efficiently during traversal.

Brute Force Approach for Binary Tree Paths

A common naive approach to solving Binary Tree Paths is to perform a Breadth-First Search (BFS) where every node in the queue stores not just the node reference, but the entire path string constructed so far.

Naive Logic

1. Initialize a queue with the root node and the string "root.val".
2. While the queue is not empty:
   • Dequeue the current node and its associated path string.
   • If the node is a leaf, add the path string to the result list.
   • If the node has a left child, create a new string (copying the current path + "->" + left val) and enqueue it.
   • Repeat for the right child.

Time Complexity Analysis

While technically correct, this approach can be memory-intensive. In a dense tree, the queue becomes very large. Furthermore, string concatenation and copying at every level in a BFS manner can lead to high constant factors in memory usage compared to a DFS approach that utilizes the call stack.

Why it is Suboptimal

While BFS finds the shortest path in unweighted graphs, "Binary Tree Paths" requires all paths. BFS does not offer an algorithmic advantage here and often requires more complex code to manage the queue of pairs (Node, String). The recursive structure of trees naturally lends itself to a DFS solution, which is generally cleaner to implement and easier to reason about for full-tree traversals.

Algorithm Strategy: Tree DFS - Recursive Preorder Traversal

We will implement a dfs helper function that takes the current node and the current_path string.

1. Base Case (Null Check): If the current node is null, return immediately. This handles edge cases and simplifies leaf logic.
2. Update Path: Append the current node's value to the current_path. If the current_path was not empty, precede the value with "->".
3. Leaf Check: Check if the current node is a leaf (i.e., node.left == null and node.right == null).
   • If yes, add the current_path to our global result list.
4. Recursive Step:
   • Call dfs on node.left with the updated current_path.
   • Call dfs on node.right with the updated current_path.

This strategy ensures we visit every node exactly once and construct paths in a top-down manner.

Execution Flow

Let's trace the algorithm with Input: root = [1, 2, 3, null, 5]

1. Call DFS(1, ""):

   • Path becomes "1".
   • Node 1 is not a leaf.
   • Recurse Left: DFS(2, "1").

2. Inside DFS(2, "1"):

   • Path becomes "1->2".
   • Node 2 is not a leaf (has right child 5).
   • Recurse Left: DFS(null, "1->2") -> Returns immediately.
   • Recurse Right: DFS(5, "1->2").

3. Inside DFS(5, "1->2"):

   • Path becomes "1->2->5".
   • Node 5 is a leaf (left and right are null).
   • Action: Add "1->2->5" to result list.
   • Returns to Node 2 context.

4. Back in DFS(2, "1"):

   • Both children processed. Returns to Node 1 context.

5. Back in DFS(1, ""):

   • Recurse Right: DFS(3, "1").

6. Inside DFS(3, "1"):

   • Path becomes "1->3".
   • Node 3 is a leaf.
   • Action: Add "1->3" to result list.
   • Returns to Node 1 context.

7. Final Result: ["1->2->5", "1->3"].

Proof of Correctness

The correctness relies on the structural induction of the binary tree:

1. Basis: For a single-node tree (root only), the algorithm appends the root value, detects it as a leaf, and returns the single correct path.
2. Inductive Step: Assume the algorithm correctly constructs paths for any subtree rooted at L (left) and R (right). When at the parent P, the algorithm constructs the prefix "Path(Root...P)". It then passes this prefix to L. By assumption, L will complete all paths starting with "Path(Root...P)->L...". The same applies to R.
3. Completeness: Since DFS visits every node, and the leaf check ensures we only store completed paths, the result contains all valid root-to-leaf paths.

Pattern Reuse Notes

The Tree DFS - Recursive Preorder Traversal pattern is highly versatile. Understanding the logic in LeetCode 257 helps with:

• LeetCode 100: Same Tree - Uses simultaneous preorder traversal to compare two trees node by node.
• LeetCode 101: Symmetric Tree - A variation where you traverse left-right and right-left simultaneously.
• LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal - Relies heavily on the definition of preorder traversal to identify root nodes recursively.
• LeetCode 114: Flatten Binary Tree to Linked List - Uses preorder traversal logic to rearrange pointers in place.

Reference Implementation

C++ Solution for LeetCode 257

1class Solution {
2public:
3    void dfs(TreeNode* node, string path, vector<string>& result) {
4        if (!node) return;
5        
6        // Append current node value
7        path += to_string(node->val);
8        
9        // Check if it is a leaf node
10        if (!node->left && !node->right) {
11            result.push_back(path);
12        } else {
13            // If not a leaf, continue traversal with arrow
14            path += "->";
15            dfs(node->left, path, result);
16            dfs(node->right, path, result);
17        }
18    }
19
20    vector<string> binaryTreePaths(TreeNode* root) {
21        vector<string> result;
22        dfs(root, "", result);
23        return result;
24    }
25};

Java Solution for LeetCode 257

1class Solution {
2    public List<String> binaryTreePaths(TreeNode root) {
3        List<String> result = new ArrayList<>();
4        if (root != null) {
5            dfs(root, "", result);
6        }
7        return result;
8    }
9
10    private void dfs(TreeNode node, String path, List<String> result) {
11        // Append current node to path
12        path += Integer.toString(node.val);
13        
14        // Check if leaf
15        if (node.left == null && node.right == null) {
16            result.add(path);
17        } else {
18            // Recurse with arrow appended
19            path += "->";
20            if (node.left != null) dfs(node.left, path, result);
21            if (node.right != null) dfs(node.right, path, result);
22        }
23    }
24}

Python Solution for LeetCode 257

1class Solution:
2    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
3        result = []
4        
5        def dfs(node, path):
6            if not node:
7                return
8            
9            # Construct current path
10            path += str(node.val)
11            
12            # If leaf, add to result
13            if not node.left and not node.right:
14                result.append(path)
15            else:
16                # Recurse
17                dfs(node.left, path + "->")
18                dfs(node.right, path + "->")
19        
20        dfs(root, "")
21        return result