Leetcode – Binary Tree Paths Solution in Python

Spread the love

Introduction

Binary Tree Paths is a classic problem in LeetCode, frequently asked in coding interviews, which deals with binary trees and depth-first search. In this detailed article, we will explore the problem statement, discuss multiple approaches to solve it, and analyze their respective time and space complexities. We will provide Python implementations for each approach.

Problem Statement

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

A leaf is a node with no children.

Input

  • root: A reference to the root node of a binary tree.

Output

  • A list of strings, where each string represents a root-to-leaf path.

Approach 1: Depth-First Search (DFS) with Recursion

This approach utilizes recursion to perform depth-first search through the binary tree.

  1. Start DFS from the root node.
  2. In the DFS, pass the current path as an argument.
  3. For each node, append it to the current path.
  4. If the current node is a leaf node, store the current path as one of the results.
  5. Recur for the left and right children of the current node, passing the updated path.
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):
        # Base case
        if not root:
            return []
        
        # List to store the paths
        paths = []
        
        # Helper function for DFS
        def dfs(node, path):
            # Append the current node's value to the path
            path += str(node.val)
            
            # If it is a leaf node, add the path to the result
            if not node.left and not node.right:
                paths.append(path)
            else:
                path += "->" # Add the arrow for non-leaf nodes
                # Recur for left and right children
                if node.left:
                    dfs(node.left, path)
                if node.right:
                    dfs(node.right, path)
        
        # Start DFS from the root
        dfs(root, "")
        
        return paths

Time Complexity

The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

Space Complexity

The space complexity is O(H), where H is the height of the tree. This accounts for the maximum size of the recursive call stack during the DFS.

Approach 2: Iterative Depth-First Search (DFS) with Stack

This approach uses an iterative DFS traversal using a stack, which simulates the behavior of the recursive approach.

  1. Initialize a stack with the root node and its path.
  2. Pop a node and its path from the stack.
  3. If it’s a leaf node, store the path as one of the results.
  4. Push the right and left children and their paths to the stack.
  5. Repeat steps 2-4 until the stack is empty.
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):
        # Base case
        if not root:
            return []
        
        # List to store the paths
        paths = []
        
        # Stack for DFS
        stack = [(root, str(root.val))]
        
        # Iterate until the stack is empty
        while stack:
            # Pop a node and its path from the stack
            node, path = stack.pop()
            
            # If it's a leaf node, add the path to the result
            if not node.left and not node.right:
                paths.append(path)
            # Push the right and left children and their paths to the stack
            if node.right:
                stack.append((node.right, path + "->" + str(node.right.val)))
            if node.left:
                stack.append((node.left, path + "->" + str(node.left.val)))
        
        return paths

Time Complexity

The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

Space Complexity

The space complexity is O(H), where H is the height of the tree. This accounts for the maximum size of the stack during the DFS.

Conclusion

We discussed the Binary Tree Paths problem on LeetCode and explored two different approaches to solving it – Recursive Depth-First Search and Iterative Depth-First Search using a stack. Both approaches have linear time complexity and are equally effective. The choice between recursive and iterative methods depends on personal preference and any specific constraints regarding space complexity or stack depth.

Leave a Reply