NUHMAN.com

Introduction

LeetCode 129: Sum Root to Leaf Numbers is a binary tree problem where the task is to find the sum of all numbers formed by root-to-leaf paths in a binary tree. Each path from root to leaf represents a number where each node in the path contributes its value multiplied by the respective place value (e.g., tens, hundreds). The goal is to compute the total sum of these numbers.

Problem Statement

Given a binary tree where each node contains a single digit, calculate the sum of all the numbers formed by the root-to-leaf paths. A leaf is a node with no children.

Note: A path represents a sequence of nodes from the root to any leaf node, and the value at each node is considered a digit in the number.

Example:

go

Input:
      1
     / \
    2   3
   / \
  4   5

Output: 102 + 103 + 124 + 125 = 454

Explanation:

• Root-to-leaf paths: 1 -> 2 -> 4, 1 -> 2 -> 5, 1 -> 3
• Corresponding numbers: 124, 125, 103
• Sum: 124 + 125 + 103 = 352

Approach:

Depth-First Search (DFS) Approach

The problem can be solved using a Depth-First Search (DFS) strategy. Here's how we can approach the problem:

1. DFS Traversal: We will traverse the binary tree from the root to each leaf node. At each node, we calculate the number formed from the root to that node by adding the current node's value to the existing number.
2. Leaf Nodes: Once a leaf node is reached, we add the number formed by the path from root to this leaf to the result.
3. Backtracking: As we backtrack from a node, we remove the effect of the current node's value and continue the traversal.
4. Edge Case: If the tree is empty, the sum should be 0.

Recursive DFS Implementation:

This solution uses recursion to implement the DFS traversal. We pass an accumulated number as we traverse down the tree.

Go Implementation

Solution Using DFS

go

package main

import "fmt"

// TreeNode is the definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// sumNumbers calculates the sum of all root-to-leaf numbers
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

// dfs performs a depth-first search to calculate the sum of numbers
func dfs(node *TreeNode, currentSum int) int {
    if node == nil {
        return 0
    }
    
    // Update the current sum by adding the current node's value
    currentSum = currentSum*10 + node.Val
    
    // If we reach a leaf node, return the current sum
    if node.Left == nil && node.Right == nil {
        return currentSum
    }
    
    // Recursively calculate the sum for left and right subtrees
    return dfs(node.Left, currentSum) + dfs(node.Right, currentSum)
}

func main() {
    // Example binary tree
    root := &TreeNode{1, 
                &TreeNode{2, 
                    &TreeNode{4, nil, nil}, 
                    &TreeNode{5, nil, nil}}, 
                &TreeNode{3, nil, nil}}

    result := sumNumbers(root)
    fmt.Println(result) // Output: 522
}

Explanation:

1. TreeNode Struct: This is the definition for the binary tree nodes. Each node has a value (Val), a left child (Left), and a right child (Right).
2. sumNumbers Function: This is the main function that initializes the DFS traversal. It starts with the root node and calls the helper function dfs.
3. dfs Function:

• Base Case: If the node is nil, we return 0 because no further path can be formed.
• Updating the Current Path Value: At each node, we multiply the current sum by 10 (to shift the digits to the left) and add the current node’s value to it.
• Leaf Node Check: If we reach a leaf node (a node with no left or right children), we return the current accumulated sum for that path.
• Recursion: For non-leaf nodes, we recursively calculate the sum for the left and right subtrees and add their results.

1. Example: In the main function, we create a simple tree and call sumNumbers to compute the result. The tree is:

markdown

      1
     / \
    2   3
   / \
  4   5

The root-to-leaf paths are 1 -> 2 -> 4, 1 -> 2 -> 5, and 1 -> 3. The corresponding numbers are 124, 125, and 103. The sum is 124 + 125 + 103 = 352.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Time Complexity:

• O(n) where n is the number of nodes in the binary tree. We visit each node exactly once.

Space Complexity:

• O(h) where h is the height of the binary tree. This is due to the recursive stack used for DFS traversal. In the worst case (unbalanced tree), the height can be O(n).

Edge Cases

1. Edge Case: Empty Tree

• Input: nil
• Output: 0
• Explanation: An empty tree has no paths, so the sum is 0.

1. Edge Case: Single Node Tree

• Input: [1]
• Output: 1
• Explanation: A single node tree represents the number itself, which is 1.

1. Edge Case: All Leaf Nodes Have No Children

• Input: [1, 2, 3]
• Output: 25
• Explanation: The tree has two leaf nodes forming paths 1 -> 2 and 1 -> 3, which gives numbers 12 and 13, and their sum is 12 + 13 = 25.

Conclusion

LeetCode 129: Sum Root to Leaf Numbers is a problem that can be effectively solved using Depth-First Search (DFS). The key is to traverse the tree while keeping track of the number formed from the root to each leaf node. This approach ensures an optimal solution with a time complexity of O(n), where n is the number of nodes in the binary tree. The space complexity is O(h) due to the recursive stack.