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

0% completed

Solution: Sum of Root To Leaf Binary Numbers
Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

You are given the root of a binary tree, where each node holds either a 0 or 1. Each path from the root to a leaf forms a binary number.

For example, if the path is 1 -> 0 -> 1, then this could represent 101 in binary, which is 5 in decimal representation. You need to consider all these root-to-leaf paths, convert them to binary numbers and sum them.

Return the total sum of all these binary numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

Examples

Example 1

  • Input: root = [1,0,1,0,1,null,1]
Image
  • Expected Output: 16
  • Explanation: The paths from the root to leaves represent binary numbers 100, 101, and 111. Their decimal equivalents are 4, 5, and 7, respectively. The sum of these numbers is 4 + 5 + 7 = 16.

Example 2

  • Input: root = [1,1,0,1,1,0,1]
Image
  • Expected Output: 23
  • Explanation: The paths represent binary numbers 111, 111, 100 and 101. Their decimal equivalents are 7, 5, 4, and 5, respectively. The sum is 7 + 7 + 4 + 5 = 23.

Example 3

  • Input: root = [1,0,1,null,null,0,1]
Image
  • Expected Output: 15
  • Explanation: The paths represent binary numbers 10, 110, and 111. Their decimal equivalents are 2, 6, and 7, respectively. The sum is 2 + 6 + 7 = 15.

Constraints:

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

Solution

To solve this problem, we can use Depth-First Search (DFS) to explore all possible paths from the root to the leaves in the binary tree. The idea is to traverse the tree while keeping track of the current binary number formed by the nodes on the path. As we move down the tree, we shift the current number to the left (which is equivalent to multiplying by 2) and add the value of the current node. Once we reach a leaf, we add the complete binary number to our sum.

This approach is effective because it directly mirrors the structure of the problem—each path from the root to a leaf naturally corresponds to a binary number, and DFS allows us to explore these paths efficiently. By accumulating the sum at each leaf, we ensure that all possible numbers are considered, leading to the correct total sum of all binary numbers in the tree.

Step-by-Step Algorithm

  1. Initialize the Process:

    • Start DFS from the root node with currentSum 0.

  2. Check for Null Node:

    • If the current node is null, return 0. This acts as the base case and helps terminate the recursive calls.

  3. Update the Current Sum:

    • Calculate the new currentSum by shifting the previous currentSum left by one bit (equivalent to multiplying by 2) and adding the value of the current node.
    • This can be represented as currentSum = currentSum * 2 + node.val.
    • For example, if you want to append 1 to 10, then you need to leftshif 10, and it will become 100, and now you can add 1 to 100. So, it will become 101.

  4. Check for Leaf Node:

    • If the current node is a leaf (i.e., both left and right children are null), return the currentSum as it represents the complete binary number from the root to this leaf.

  5. Recursive Traversal:

    • Recursively call the dfs method for the left child of the current node and add the result to a sum.
    • Recursively call the dfs method for the right child of the current node and add the result to the sum.
    • Return the sum obtained from both left and right subtree traversals.

  6. Combine Results:

    • In the sumRootToLeaf method, the final returned sum from the dfs method represents the total sum of all root-to-leaf binary numbers.

Algorithm Walkthrough

Let's walk through the algorithm with the example binary tree [1,0,1,0,1,null,1].

Image

  1. Starting at Root Node:

    • The root node is 1. We start the DFS traversal with currentSum = 0.
    • Update currentSum: currentSum = 0 * 2 + 1 = 1.

  2. Move to Left Child (0):

    • Move to the left child of root, which is 0.
    • Update currentSum: currentSum = 1 * 2 + 0 = 2.

  3. Move to Left Child (0):

    • Move to the left child of the previous node, which is 0.
    • Update currentSum: currentSum = 2 * 2 + 0 = 4.
    • Since this node is a leaf, return 4.

  4. Backtrack and Move to Right Child (1):

    • Backtrack to the node with value 0 (parent node).
    • Move to its right child, which is 1.
    • Update currentSum: currentSum = 2 * 2 + 1 = 5.
    • Since this node is a leaf, return 5.

  5. Backtrack to Root and Move to Right Child (1):

    • Backtrack to the root node.
    • Move to its right child, which is 1.
    • Update currentSum: currentSum = 1 * 2 + 1 = 3.

  6. Move to Right Child (1):

    • Move to the right child of the previous node, which is 1.
    • Update currentSum: currentSum = 3 * 2 + 1 = 7.
    • Since this node is a leaf, return 7.

  7. Combine Results:

    • Sum the values from all leaf nodes: 4 + 5 + 7 = 16.

  8. Final Output:

    • The total sum of all root-to-leaf binary numbers is 16.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • The time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree.
  • This is because the algorithm performs a Depth First Search (DFS), which visits each node exactly once.

Space Complexity

  • The space complexity is O(H), where H is the height of the tree.
  • This space is required for the recursive stack used during DFS. In the worst case, if the tree is skewed, the height H could be equal to N, leading to a space complexity of O(N).
  • In the best case, the tree is balanced, and the space complexity would be O(log N).
Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity