Binary Tree Paths

---

Intuition

• Similar to a seen set, use a list to keep track of all the nodes visited.
• You are at a leaf node there exists no left or right node from the current node. In that case, simply join the nodes you have seen so far into a result.

Complexity

Runtime

$O(N)$ to traverse through every node

Space

$O(N)$ since cur could contain every node in the case of a long chain going, for example, only left.

Code

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        cur = []
        res = []
        def r(node):
            if not node:
                return
 
            cur.append(str(node.val))
            
            if not (node.left or node.right):
                res.append('->'.join(cur))
 
            r(node.left)
            r(node.right)
 
            cur.pop()
 
        r(root)
        return res

Cards

START Basic Front: Binary Tree Paths Back: Store the nodes you have seen so far similarly to how is done with a seen set.

END

---

References

• Binary Tree Paths