Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Solution: Binary Tree Paths
Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity:

Problem Statement

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

Examples

Example 1:

  • Input: root = [1,2,3,null,null,4,5]
Image
  • Expected Output: ["1->2", "1->3->4", "1->3->5"]
  • Justification: The binary tree has one root-to-leaf path for the left child (1->2) and two for the right child, branching into 4 and 5 respectively.

Example 2:

  • Input: root = [5,3,6,2,4,null,null,1]
Image
  • Expected Output: ["5->3->2->1", "5->3->4", "5->6"]
  • Justification: There are three paths leading to leaf nodes: one through the left subtree down to 1, another through the left subtree to 4, and one path through the right subtree to 6.

Example 3:

  • Input: root = [2,null,3,null,4,null,5]
Image
  • Expected Output: ["2->3->4->5"]
  • Justification: There's only one path from the root to the leaf, cascading down the right children.

Solution

To solve this problem, we will employ a depth-first search (DFS) approach. DFS is particularly well-suited for this task because it allows us to explore each branch of the tree to its fullest extent (down to the leaf nodes) before backtracking. This ensures that we can collect all root-to-leaf paths efficiently. The algorithm works by traversing the tree from the root node, appending the value of each visited node to a path string, and recursively exploring all possible paths down to the leaf nodes. Once a leaf node is reached, the current path string is added to a list of paths. This method is applied recursively to each node's left and right children if they exist. By using DFS, we can guarantee that all paths are explored, and the use of recursion simplifies the traversal logic.

Our approach is effective because it aligns with the natural structure of binary trees, allowing us to leverage their hierarchical nature to efficiently navigate and record paths. DFS ensures that no node is missed and that each path is fully recorded before moving on to the next. This strategy is optimal for this problem because it minimizes unnecessary computations and visits each node exactly once, ensuring all unique root-to-leaf paths are captured.

Step-by-Step Algorithm

  1. Start at the Root: Begin the process with the root node of the binary tree.

  2. Initialize Paths List: Create an empty list to store the paths from the root to each leaf.

  3. Recursive Function - findPaths: Define a recursive function that takes the current node, the path so far (as a string), and the paths list as arguments. This function will be used to explore all possible paths from the root to the leaves.

  4. Base Case: In the recursive function, check if the current node is null. If it is, return immediately, as this path cannot lead to a leaf.

  5. Update Path: Append the current node's value to the path string. If the current node is not null, this means we are on a potential path to a leaf.

  6. Leaf Node Check: Check if the current node is a leaf (i.e., both its left and right children are null). If it is, add the current path to the paths list as a complete root-to-leaf path.

  7. Recursive Exploration: If the current node is not a leaf, recursively call the function on both the left and right children of the current node, if they exist. Before making the recursive call, add "->" to the path string to indicate the path's continuation.

  8. Return Paths: After all recursive calls complete, return the paths list containing all root-to-leaf paths found.

Algorithm Walkthrough

Image

  1. Start at Root (5): The path starts with "5".

  2. Move to Left Child (3): The path updates to "5->3". Since 3 is not a leaf, continue down.

  3. Explore Left of 3 (2): Path updates to "5->3->2". 2 is not a leaf; it has a right child.

    • Move to Right of 2 (1): Path is "5->3->2->1". 1 is a leaf, so add "5->3->2->1" to paths.

  4. Backtrack to 3 and Go Right (4): Path from 5 is "5->3". Now update path to "5->3->4". 4 is a leaf, so add "5->3->4" to paths.

  5. Backtrack to 5 and Move to Right Child (6): Now explore the right side of 5. The path is "5->6". Since 6 is a leaf, add "5->6" to paths.

Completed Paths:

  • By following the steps above, the algorithm discovers all paths:
    • "5->3->2->1"
    • "5->3->4"
    • "5->6"

These steps systematically explore each branch of the tree, ensuring that every unique root-to-leaf path is identified and recorded.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity:

  • O(N): Where N is the number of nodes in the binary tree. In the worst case, we visit each node exactly once to either extend the path string or to backtrack.

Space Complexity:

  • O(N): In the worst-case scenario, the space complexity is determined by the height of the binary tree, which influences the recursion stack depth. For a skewed binary tree (one where every parent node has only one child), the height of the tree can be N, leading to a space complexity of O(N).
Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: