#1022

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Sum of Root To Leaf Binary Numbers

Calculate the sum of binary numbers from root to leaf paths in a binary tree.

Problem Statement

You are given the root of a binary tree where each node contains a value of either 0 or 1. Each path from the root to a leaf node represents a binary number with the most significant bit at the root. You need to calculate the sum of these binary numbers, treating each path as a unique binary number, and returning the sum of all such numbers.

The leaf nodes are the end points of the paths, and every path from the root to each leaf node must be treated as a binary number. The answer should be the sum of the binary values of all these paths. You can assume that the answer fits within a 32-bit integer, and the number of nodes in the tree will be between 1 and 1000.

Examples

Example 1

Input: root = [1,0,1,0,1,0,1]

Output: 22

(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2

Input: root = [0]

Output: 0

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 1000].
Node.val is 0 or 1.

Solution Approach

Depth-First Search (DFS)

Use a DFS approach to traverse the tree. Starting at the root, propagate a binary number constructed from the path. For each leaf node, the accumulated binary number can be converted to its decimal equivalent and added to the sum.

Binary to Decimal Conversion

During the DFS traversal, maintain a running binary number by shifting the previous number and adding the current node’s value. When a leaf is reached, convert the binary number to its decimal equivalent by summing it directly.

Backtracking and State Tracking

Backtrack during the DFS, ensuring that each binary number is correctly computed for every root-to-leaf path. This involves maintaining state across the recursive calls to track the binary path.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once. The space complexity is O(H), where H is the height of the tree, due to the space required for recursion stack in DFS. The height of the tree in the worst case could be O(N) for skewed trees, but typically, it is O(log N) for balanced trees.

What Interviewers Usually Probe

Tests depth-first traversal understanding and binary tree manipulation.
Evaluates candidate's ability to manage recursive state and path tracking.
Requires proficiency in converting binary representations to decimal.

Common Pitfalls or Variants

Common pitfalls

Failing to handle tree nodes correctly, especially when transitioning from one binary number to another.
Not correctly converting the binary number to decimal or mishandling the sum.
Incorrectly managing recursion depth or state during backtracking, leading to incorrect results.

Follow-up variants

Use a breadth-first search (BFS) instead of DFS for tree traversal.
Consider a solution where you track the path using a list and convert at the end of the traversal.
Implement an iterative DFS using an explicit stack to avoid recursion.

FAQ

What is the best way to approach the 'Sum of Root To Leaf Binary Numbers' problem?

A depth-first search (DFS) is a solid approach to traverse the binary tree while constructing binary numbers from root to leaf. Convert each binary path to decimal once a leaf is reached, and sum the results.

How do you convert a binary number from a tree path into decimal?

To convert a binary path, maintain a running binary number by shifting the previous value and adding the current node's value. At the leaf, convert the binary number to decimal by using base-2 conversion.

How does state tracking work in this problem?

State tracking is crucial in DFS to ensure that the binary number is correctly built as you traverse down the tree. Each recursive call should carry the current binary value to the next node.

What are the time and space complexities for this problem?

Time complexity is O(N), where N is the number of nodes, as we visit each node once. Space complexity is O(H), where H is the height of the tree, due to recursion stack usage.

What if the tree is skewed, and depth becomes large?

For skewed trees, the height could reach N, which would make the space complexity O(N). However, this approach is still valid, and the solution will handle it correctly.

terminal

Solution

Solution 1: Recursion

We design a recursive function $\text{dfs}(root, t)$, which takes two parameters: the current node $root$ and the binary number $t$ corresponding to the parent node of the current node. The return value of the function is the sum of binary numbers represented by paths from the current node to leaf nodes. The answer is $\textrm{dfs}(root, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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 sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode], x: int) -> int:
            if root is None:
                return 0
            x = x << 1 | root.val
            if root.left == root.right:
                return x
            return dfs(root.left, x) + dfs(root.right, x)

        return dfs(root, 0)

Continue Practicing

#1026 maximum difference between node and ancestor #1028 recover a tree from preorder traversal #1038 binary search tree to greater sum tree