DSA problem
Binary Tree Paths
Given the root of a binary tree, return all root-to-leaf paths in any order. Each path should be represented as a string with arrow separators, e.g. "1->2->5". A leaf is a node with no children.
This is the prototypical preorder DFS with a "carry-state" pattern: we accumulate the current path as we descend and emit it whenever we reach a leaf. The recurrence is: append the current node's value to the running path; if the node has no children, append the path to the output list; otherwise recurse into each non-null child.
Two implementation styles are common. The immutable-string style passes the partial path as a string and concatenates a new copy at every step — readable but quadratic in path length due to repeated allocation. The mutable-list style appends to a list before recursing and pops after, joining only when a leaf is reached — this version is O(n) total work, where n counts both nodes and characters output.
Time complexity is O(n * h) in the worst case because writing out each path costs O(h) characters and there can be Θ(n / h) leaves (so total output is Θ(n)). Space complexity is O(h) for the recursion plus O(n) for the output strings themselves.
Examples
root = [1,2,3,null,5]["1->2->5","1->3"]root = [1]["1"]root = [1,2,3,4,null,null,5]["1->2->4","1->3->5"]Constraints
- The number of nodes in the tree is in the range [1, 100].
- -100 <= Node.val <= 100
- The tree contains at least one node.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.