We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Paths

Number: 257

Difficulty: Easy

Paid? No

Companies: Meta, Google, Apple, Microsoft

Problem Description

Given the root of a binary tree, return all root-to-leaf paths as strings where each node is separated by "->". A leaf is defined as a node with no children.

Key Insights

  • Use a Depth-First Search (DFS) or backtracking approach to explore all paths from the root to leaves.
  • Build the path as you traverse the tree.
  • Once a leaf node is reached, append the constructed path to the result list.
  • The problem requires returning all paths in any order.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since every node is visited once. Space Complexity: O(H), where H is the height of the tree, which is the space used on the recursion stack. In the worst case (skewed tree), H can be O(N).

Solution

We perform a DFS traversal starting from the root. At each node, we append the node's value to the current path. If the current node is a leaf (i.e. it does not have left or right children), we add the current path (constructed as a string separated by "->") to the result. Otherwise, we recursively process the left and right children. The recursion naturally handles backtracking since the current path is passed (or extended) at each recursive call.

Code Solutions

# 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

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # List to store the final root-to-leaf paths.
        result = []
        
        # Helper function to perform DFS on the tree.
        def dfs(node, current_path):
            if not node:
                return
            # Append current node's value to the path.
            if current_path:
                current_path += "->" + str(node.val)
            else:
                current_path = str(node.val)
            # If the node is a leaf, add the path to result.
            if not node.left and not node.right:
                result.append(current_path)
                return
            # Continue DFS on the left and right children.
            if node.left:
                dfs(node.left, current_path)
            if node.right:
                dfs(node.right, current_path)
        
        # Initiate DFS from the root.
        dfs(root, "")
        return result
← Back to All Questions