Binary Tree Paths solution and explanation
Google
9 more videos on this problem
LeetCode 257. Binary Tree Paths (Algorithm Explained)Nick White · 9:24 · 30K views
(Remade) Binary Tree Paths | Depth First Search | Leetcode 257Nideesh Terapalli · 6:01 · 4K views
257. Binary Tree Paths (Leetcode Easy)Programming Live with Larry · 4:50 · 3K views
Print All Paths In Binary Tree | LeetCode 257Java2Novice · 9:01 · 2K views
Binary Tree Paths - LeetCode 257 - JavaScriptAlgoJS · 6:15 · 1K views
(Old) Leetcode 257 - Binary Tree Paths | Depth First SearchNideesh Terapalli · 5:27 · 678 views
Leetcode 257 Binary Tree Paths - Amazon Interview QuestionAlgorithmicIQ · 9:23 · 600 views
Binary Tree Paths | LEETCODE - 257 | Easy solutionhi-malik · 5:53 · 567 views
Mastering Binary Tree Paths: Easy LeetCode Q. 257 | Backtracking, DFS | Amazon, Infosys, OLAProgramming Pathshala · 25:33 · 490 views
LeetCode 257 | Binary Tree Paths | Easy | Efficient Solution Explained |Code Scribbler · 3:41 · 263 views
The problem
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 overview
Problem Overview: Given the root of a binary tree, return every path from the root node to each leaf node. Each path must be represented as a string in the format node1->node2->node3. A leaf node is a node with no children, so a valid path ends only when both left and right pointers are null.
Approach 1: Depth-First Search (DFS) - Recursive (O(n) time, O(h) space)
The most natural way to solve this problem is with recursive Depth-First Search. Start from the root and carry the current path as a string while traversing the tree. At each node, append its value to the path. When you reach a leaf node, store the completed path in the result list. The recursion then backtracks and explores the remaining branches.
This approach works because DFS naturally explores one root-to-leaf path at a time. The recursion stack keeps track of the traversal state while you build the path incrementally. Each node is visited exactly once, giving a time complexity of O(n), where n is the number of nodes. The space complexity is O(h) due to the recursion stack, where h is the height of the binary tree. In skewed trees this becomes O(n), while balanced trees keep it closer to O(log n). This solution is concise and commonly expected in interviews.
Approach 2: Iterative DFS using a Stack (O(n) time, O(h) space)
The same traversal can be implemented iteratively using an explicit stack instead of recursion. Each stack entry stores a pair: the current node and the path string built so far. Pop an element, extend the path with the current node's value, and push its children back onto the stack with updated paths.
When the algorithm pops a node that has no left or right child, the path represents a complete root-to-leaf sequence and gets added to the result list. This method mirrors recursive DFS but avoids relying on the call stack. It still visits each node once, so the time complexity remains O(n). The stack holds at most one branch of nodes at a time, giving a space complexity of O(h). Iterative DFS is useful when recursion depth might be large or when you want explicit control over traversal order.
Both methods rely on tree traversal fundamentals from tree algorithms and follow a path-building pattern often used in backtracking style problems where partial results grow as you move deeper in the structure.
Recommended for interviews: Recursive DFS is the approach most interviewers expect. It demonstrates clear understanding of tree traversal and keeps the code short and readable. Mentioning the iterative stack version shows deeper knowledge of how recursion translates to explicit data structures and how to avoid recursion limits.
Approach 1: Approach 1: Depth-First Search (DFS) - Recursive
This approach uses Depth-First Search (DFS) to explore all paths from the root to the leaf nodes. Starting from the root, we recursively visit each node, accumulating the current path. When a leaf node is reached, we add the accumulated path to a list of paths. This can be implemented recursively and is optimal given the constraints.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
def dfs(node, path):
if node:
path += str(node.val)
if not node.left and not node.right: # Leaf node
paths.append(path)
else:
path += '->'
dfs(node.left, path)
dfs(node.right, path)
paths = []
dfs(root, '')
return pathsimport java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root != null) dfs(root, "", paths);
return paths;
}
private void dfs(TreeNode node, String path, List<String> paths) {
if (node != null) {
path += Integer.toString(node.val);
if (node.left == null && node.right == null) { // Leaf
paths.add(path);
} else {
path += "->";
dfs(node.left, path, paths);
dfs(node.right, path, paths);
}
}
}
}#include <vector>
#include <string>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode* node, std::string path, std::vector<std::string>& paths) {
if (!node) return;
path += std::to_string(node->val);
if (!node->left && !node->right) {
paths.push_back(path);
} else {
path += "->";
dfs(node->left, path, paths);
dfs(node->right, path, paths);
}
}
std::vector<std::string> binaryTreePaths(TreeNode* root) {
std::vector<std::string> paths;
dfs(root, "", paths);
return paths;
}var binaryTreePaths = function(root) {
const paths = [];
const dfs = (node, path) => {
if (node) {
path += node.val;
if (!node.left && !node.right) {
paths.push(path);
} else {
path += '->';
dfs(node.left, path);
dfs(node.right, path);
}
}
};
dfs(root, '');
return paths;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* node, char* path, char** paths, int* size) {
if (!node) return;
char buffer[16];
sprintf(buffer, "%d", node->val);
if (strlen(path) != 0) {
strcat(path, "->");
}
strcat(path, buffer);
if (!node->left && !node->right) {
paths[*size] = strdup(path);
(*size)++;
} else {
char temp[512];
strcpy(temp, path);
dfs(node->left, path, paths, size);
strcpy(path, temp);
dfs(node->right, path, paths, size);
}
}
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
char** paths = (char**)malloc(100 * sizeof(char*));
char path[512] = "";
*returnSize = 0;
dfs(root, path, paths, returnSize);
return paths;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<string> BinaryTreePaths(TreeNode root) {
List<string> paths = new List<string>();
if (root != null) Dfs(root, "", paths);
return paths;
}
private void Dfs(TreeNode node, string path, List<string> paths) {
if (node != null) {
path += node.val;
if (node.left == null && node.right == null) { // Leaf node
paths.Add(path);
} else {
path += "->";
Dfs(node.left, path, paths);
Dfs(node.right, path, paths);
}
}
}
}This Python solution leverages the recursive DFS approach to gather paths. Leaf nodes signal the end of a path, which is then appended to the results.
Time Complexity: O(n), as each node is visited.
Space Complexity: O(n), for the recursion stack and list storage.
Approach 2: Approach 2: Iterative DFS using a Stack
This approach utilizes an iterative Depth-First Search (DFS) with a stack. By storing the nodes and their paths on the stack, we can simulate the recursive DFS stack. This allows for constructing the paths through iterative backtracking.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root: return []
stack, paths = [(root, str(root.val))], []
while stack:
node, path = stack.pop()
if not node.left and not node.right:
paths.append(path)
if node.right:
stack.append((node.right, path + '->' + str(node.right.val)))
if node.left:
stack.append((node.left, path + '->' + str(node.left.val)))
return pathsimport java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) return paths;
Stack<Pair<TreeNode, String>> stack = new Stack<>();
stack.push(new Pair<>(root, "" + root.val));
while (!stack.isEmpty()) {
Pair<TreeNode, String> cur = stack.pop();
TreeNode node = cur.getKey();
String path = cur.getValue();
if (node.left == null && node.right == null) {
paths.add(path);
}
if (node.right != null) {
stack.push(new Pair<>(node.right, path + "->" + node.right.val));
}
if (node.left != null) {
stack.push(new Pair<>(node.left, path + "->" + node.left.val));
}
}
return paths;
}
}
// Additional class required for Pair functionality
class Pair<K, V> {
private final K key;
private final V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() { return key; }
public V getValue() { return value; }
}#include <vector>
#include <string>
#include <stack>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
std::vector<std::string> binaryTreePaths(TreeNode* root) {
std::vector<std::string> paths;
if (!root) return paths;
std::stack<std::pair<TreeNode*, std::string>> stack;
stack.push({root, std::to_string(root->val)});
while (!stack.empty()) {
auto [node, path] = stack.top(); stack.pop();
if (!node->left && !node->right) {
paths.push_back(path);
}
if (node->right) {
stack.push({node->right, path + "->" + std::to_string(node->right->val)});
}
if (node->left) {
stack.push({node->left, path + "->" + std::to_string(node->left->val)});
}
}
return paths;
}var binaryTreePaths = function(root) {
if (!root) return [];
const stack = [[root, String(root.val)]];
const paths = [];
while (stack.length) {
const [node, path] = stack.pop();
if (!node.left && !node.right) {
paths.push(path);
}
if (node.right) {
stack.push([node.right, path + '->' + node.right.val]);
}
if (node.left) {
stack.push([node.left, path + '->' + node.left.val]);
}
}
return paths;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct StackNode {
struct TreeNode* node;
char path[512];
struct StackNode* next;
};
// Utility function to create a new Stack Node
struct StackNode* newStackNode(struct TreeNode* node, const char* path) {
struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
stackNode->node = node;
strcpy(stackNode->path, path);
stackNode->next = NULL;
return stackNode;
}
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// Push an item to the stack
void push(struct StackNode** root, struct TreeNode* node, const char* path) {
struct StackNode* stackNode = newStackNode(node, path);
stackNode->next = *root;
*root = stackNode;
}
// Pop an item from the stack
char* pop(struct StackNode** root) {
if (!(*root)) return NULL;
struct StackNode* temp = *root;
(*root) = (*root)->next;
char* res = temp->path;
free(temp);
return res;
}
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
if (!root) { *returnSize = 0; return NULL; }
char** paths = (char**)malloc(100 * sizeof(char*));
struct StackNode* stack = NULL;
char path[512];
sprintf(path, "%d", root->val);
push(&stack, root, path);
*returnSize = 0;
while (stack) {
struct StackNode* current = stack;
stack = stack->next;
struct TreeNode* node = current->node;
strcpy(path, current->path);
if (!node->left && !node->right) {
paths[*returnSize] = strdup(path);
(*returnSize)++;
}
if (node->right) {
char newPath[512];
sprintf(newPath, "%s->%d", path, node->right->val);
push(&stack, node->right, newPath);
}
if (node->left) {
char newPath[512];
sprintf(newPath, "%s->%d", path, node->left->val);
push(&stack, node->left, newPath);
}
}
return paths;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<string> BinaryTreePaths(TreeNode root) {
List<string> paths = new List<string>();
if (root == null) return paths;
Stack<(TreeNode, string)> stack = new Stack<(TreeNode, string)>();
stack.Push((root, root.val.ToString()));
while (stack.Count > 0) {
var (node, path) = stack.Pop();
if (node.left == null && node.right == null) {
paths.Add(path);
}
if (node.right != null) {
stack.Push((node.right, path + "->" + node.right.val));
}
if (node.left != null) {
stack.Push((node.left, path + "->" + node.left.val));
}
}
return paths;
}
}Using a stack with tuples comprising nodes and path strings, this Python solution iteratively processes the tree. Leaf nodes add completed paths to the paths list, leveraging stack operations for state management.
Time Complexity: O(n), with n being the number of nodes.
Space Complexity: O(n), based on stack and list usage.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function binaryTreePaths(root: TreeNode | null): string[] {
const ans: string[] = [];
const t: number[] = [];
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
t.push(root.val);
if (!root.left && !root.right) {
ans.push(t.join('->'));
} else {
dfs(root.left);
dfs(root.right);
}
t.pop();
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths(root *TreeNode) (ans []string) {
t := []string{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
t = append(t, strconv.Itoa(root.Val))
if root.Left == nil && root.Right == nil {
ans = append(ans, strings.Join(t, "->"))
} else {
dfs(root.Left)
dfs(root.Right)
}
t = t[:len(t)-1]
}
dfs(root)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search (DFS) - Recursive | Time Complexity: O(n), as each node is visited. |
| Approach 2: Iterative DFS using a Stack | Time Complexity: O(n), with n being the number of nodes. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Best general solution. Clean and concise for exploring root-to-leaf paths. |
| Iterative DFS (Stack) | O(n) | O(h) | Useful when avoiding recursion depth limits or when implementing explicit traversal control. |
Frequently asked questions
Is Binary Tree Paths easy or hard?
Binary Tree Paths is classified as an Easy problem. The main concept is performing a DFS traversal while building strings representing root-to-leaf paths, which makes it a common introductory problem for practicing binary tree recursion.
How to solve Binary Tree Paths in O(n)?
Perform a DFS traversal starting from the root while maintaining the current path. Append the node value to the path as you move deeper. When a leaf node is encountered, add the completed path string to the results. Since each node is processed once, the overall complexity stays O(n).
What is the best approach for Binary Tree Paths?
Depth-First Search (DFS) using recursion is the most common approach. You traverse from the root to every leaf while building a path string along the way. When a leaf node is reached, the constructed path is added to the result. This method visits each node once and runs in O(n) time.
What data structure is used in Binary Tree Paths?
The core data structure is a binary tree. The solution typically uses recursion (implicit stack) or an explicit stack for DFS traversal, along with a list or array to store the resulting path strings.
What is the time complexity of Binary Tree Paths?
The time complexity is O(n) because each node in the binary tree is visited exactly once during the DFS traversal. Additional string construction happens along the traversal path, but it remains proportional to the number of nodes overall.
Binary Tree Paths Python or Java solution approach?
Both Python and Java solutions typically use recursive DFS. The function receives the current node and the path string so far. If the node is a leaf, the path is added to the result list; otherwise, recursion continues with the left and right children.
Is Binary Tree Paths asked at Google, Amazon, or Meta interviews?
Binary tree traversal problems like Binary Tree Paths appear frequently in interviews at companies such as Amazon, Google, and Meta. The question tests understanding of DFS traversal, recursion, and path construction within tree structures.