algoadvance

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Clarifying Questions

1. What is the structure of the tree?
   • The tree is a typical binary tree where each node has at most two children.
2. What is the representation of the tree nodes?
   • Each node is represented by a class TreeNode, which has three attributes: val (the value of the node), left (pointer to the left child), and right (pointer to the right child).
3. What should be the format of the result?
   • The result should be a list of strings, where each string represents a root-to-leaf path formatted as “root->node1->node2->…->leaf”.

Strategy

1. Depth-First Search (DFS):
   • We will use a recursive approach to traverse the tree.
   • For each node, we will explore its left and right children if they exist.
   • When we reach a leaf node (i.e., both left and right children are None), we will append the current path to the result list.
2. Path Tracking:
   • We will maintain the current path as we traverse the tree.
   • When going deeper into the tree, we add the current node’s value to the path.
   • When backtracking, we remove the current node’s value from the path.
3. Edge Cases:
   • If the tree is empty (i.e., the root is None), we return an empty list.

Code

from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root: Optional[TreeNode]) -> List[str]:
    def dfs(node: TreeNode, path: List[int], paths: List[str]):
        if node is None:
            return
        # Add current node to the path
        path.append(node.val)
        # If it's a leaf node, record the path
        if not node.left and not node.right:
            paths.append("->".join(map(str, path)))
        else:
            # Recur on the left and right subtree
            dfs(node.left, path, paths)
            dfs(node.right, path, paths)
        # Backtrack
        path.pop()
    
    paths = []
    dfs(root, [], paths)
    return paths

Time Complexity

• Time Complexity: (O(N)), where (N) is the number of nodes in the tree. This is because we visit each node exactly once.
• Space Complexity:
  • The recursion stack will hold at most (O(H)) frames, where (H) is the height of the tree. In the worst case (unbalanced tree), this is (O(N)).
  • The path storage will take up (O(N \cdot L)) space in the worst case, where (L) is the average length of the paths, resulting from the storage of all paths.

This approach is efficient given the constraints and provides clear and concise root-to-leaf paths.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?