257. Binary Tree Paths

Quick Identifier

• Topic: trees
• Pattern: Tree DFS + backtracking and DFS / backtracking
• Difficulty: Easy
• Companies: Google, Apple, Meta, Amazon, Bloomberg
• Frequency: Medium
• LeetCode: 257

Quick Sights

• Time Complexity: O(n²) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree, return all strings representing root-to-leaf paths, formatted as values joined by "->".

Concept Explanation

Given the root of a binary tree, return all strings representing root-to-leaf paths, formatted as values joined by "->".

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Enumerate every root-to-leaf path as a string (or list)
• Backtracking with path buffer, or prefix strings while walking
• Leaf detection: both children absent

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — build new string at each edge — O(n²) worst copying.
• Optimal — DFS with mutable slice + join at leaves only — O(n²) worst total characters output, O(h) active storage.

Optimal Solution

Go

package main

import "strconv"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func binaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return []string{}
	}
	result := []string{}
	var walk func(*TreeNode, []string)
	walk = func(node *TreeNode, prefix []string) {
		next := append(prefix, strconv.Itoa(node.Val))
		if node.Left == nil && node.Right == nil {
			line := next[0]
			for index := 1; index < len(next); index++ {
				line += "->" + next[index]
			}
			result = append(result, line)
			return
		}
		if node.Left != nil {
			walk(node.Left, next)
		}
		if node.Right != nil {
			walk(node.Right, next)
		}
	}
	walk(root, []string{})
	return result
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function binaryTreePaths(root) {
	if (root === null) {
		return [];
	}
	const result = [];
	function walk(node, prefixParts) {
		const nextParts = prefixParts.concat(String(node.val));
		if (node.left === null && node.right === null) {
			result.push(nextParts.join('->'));
			return;
		}
		if (node.left !== null) {
			walk(node.left, nextParts);
		}
		if (node.right !== null) {
			walk(node.right, nextParts);
		}
	}
	walk(root, []);
	return result;
}

Walkthrough

Tree 1 / 2,3 / 5 (only 2 has left 5).

Invariant: prefixParts always equals values on the path from root to node; only leaves finalize a string.

Edge Cases

• Single-node tree → one string "val"
• Skewed tree → many strings, each length proportional to depth

Pitfalls

• Treating a node with one missing child as a leaf (must have both children nil for leaf in binary tree definition here—actually if one child nil and other non-nil, not a leaf)
• Exponential string concatenation in hot loop—join at leaf keeps work tighter

Similar Problems

• 113. Path Sum II — paths filtered by target sum.
• 437. Path Sum III — path sums without fixed endpoints.
• 102. Binary Tree Level Order Traversal — different organization of nodes, still traversal fluency.

Variants

• Return arrays of ints instead of strings.
• Paths not restricted to leaves (internal endpoints)—adjust base case.

Mind-Map Tags

#trees #backtracking #root-to-leaf #string-build #dfs