What is the brute force approach and complexity for Binary Tree Paths?

Pass the path string by value, so every call works on its own copy with time complexity O(N · H) and space complexity O(H²).

What is the optimal approach and complexity for Binary Tree Paths?

Push a value on the way down, pop it on the way up, and build a string only at leaves with optimal time complexity O(N · H) and space complexity O(H).

How do you identify the pattern for Binary Tree Paths?

Look for key signals in the prompt: "every root-to-leaf path" indicates Visit every leaf, so a full DFS. The answer is a list, not one number.; "return them as strings" indicates The path must be kept as values that can be joined into text at the leaf.; "root-to-leaf" indicates Only leaves end a path. A node with one child is not an end..

Binary Tree Paths

Easy·LeetCode #257 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given the root of a binary tree.

Return every root-to-leaf path as a string. Put -> between two values, for example 1->2->5. Do not put an arrow before the first value or after the last one. A leaf is a node with no children.

Input

The root of a binary tree. It has at least one node.

Output

A list of strings, one for each root-to-leaf path.

Example 1

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

Output: ["1->2->5", "1->3"]

Node 2 has only a right child, so the path continues to 5. Node 3 is a leaf, so the path 1 → 3 ends there.

Example 2

Input: root = [1]

Output: ["1"]

The root is also a leaf, so its only path is just its value.

Constraints

• The tree has between 1 and 100 nodes.
• −100 ≤ Node.val ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“every root-to-leaf path”

→ Visit every leaf, so a full DFS. The answer is a list, not one number.

“return them as strings”

→ The path must be kept as values that can be joined into text at the leaf.

“root-to-leaf”

→ Only leaves end a path. A node with one child is not an end.

Approach Complexity Ladder

Brute Force — copy the path string into every callO(N · H)O(H²)

Pass the path string by value, so every call works on its own copy

Optimal — one shared path with push and popO(N · H)O(H)

Push a value on the way down, pop it on the way up, and build a string only at leaves

Brute Force Intuition

Pass the string built so far as a parameter. Each call adds its node's value, then gives each child its own copy with -> added. Because each call has its own string, nothing has to be undone. The cost is in the copies.

Recognition rule for this sub-pattern:

Carry information down the path (current sum, max so far, direction). Check it at leaves.

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture