Binary Tree Paths
Easy · Graphs · Explanation and code example
Root-to-Leaf DFS Paths
How it works
Maintain a shared path prefix during depth-first search. At a leaf, join the prefix and leaf value into one output string. Append before visiting children and remove afterward so the next sibling receives the correct path.
Steps
- Visit the current node and test whether it is a leaf.
- Save a complete root-to-leaf string at leaves.
- Append the current prefix for child visits, then pop it.
Complexity
- Time: O(n + K) for n nodes and K returned characters, under fixed-width node values.
- Space: O(h) working path/stack plus O(K) output.
Things to watch for
- Only leaves finish a path.
- Backtrack after both child calls.
- Keep separators between values, with none after the final value.
Python code example
class Solution:
def binaryTreePaths(self, root: TreeNode | None) -> list[str]:
ans = []
def dfs(root: TreeNode | None, path: list[str]) -> None:
if not root:
return
if not root.left and not root.right:
ans.append(''.join(path) + str(root.val))
return
path.append(str(root.val) + '->')
dfs(root.left, path)
dfs(root.right, path)
path.pop()
dfs(root, [])
return ans
C++ code example
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
dfs(root, {}, ans);
return ans;
}
private:
void dfs(TreeNode* root, vector<string>&& path, vector<string>& ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
ans.push_back(join(path) + to_string(root->val));
return;
}
path.push_back(to_string(root->val) + "->");
dfs(root->left, std::move(path), ans);
dfs(root->right, std::move(path), ans);
path.pop_back();
}
string join(const vector<string>& path) {
string joined;
for (const string& s : path)
joined += s;
return joined;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.