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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Paths

Difficulty: Easy

Problem Description

Given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.

Key Insights

  • Paths in a binary tree can be explored using Depth-First Search (DFS).
  • Each path is represented as a string that connects node values with a "->".
  • We need to identify leaf nodes to complete a path.
  • Backtracking can help us explore different paths effectively.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, since we must visit each node once. Space Complexity: O(H), where H is the height of the tree, which accounts for the space used by the recursion stack.

Solution

To find all root-to-leaf paths, we can use a Depth-First Search (DFS) approach. We will traverse the tree starting from the root and keep track of the current path as we move down the tree. When we reach a leaf node, we will store the current path. The paths will be constructed as strings, where node values are joined by "->". The algorithm will utilize recursion to explore all possible paths.

Code Solutions

def binaryTreePaths(root):
    def dfs(node, path):
        if node:
            path += str(node.val)
            # If it's a leaf node, add the path to results
            if not node.left and not node.right:
                paths.append(path)
            else:
                path += "->"  # Add the arrow for non-leaf nodes
                dfs(node.left, path)
                dfs(node.right, path)

    paths = []
    dfs(root, "")
    return paths
← Back to All Questions