1022. Sum of Root To Leaf Binary Numbers

EasyTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

In this problem, we are presented with the root of a binary tree where each node contains a binary digit, either 0 or 1. The goal is to calculate the sum of all the numbers formed by the paths from the root to each leaf node. A path represents a binary number with the most significant bit at the root and the least significant bit at a leaf.

To visualize this concept, imagine traversing down the tree from the root to a leaf. Along the way, each time we move from a parent to a child node, we append the value of the child node to the right of the current binary number we have. When we reach a leaf, we have formed a complete binary number that can be converted to its decimal equivalent. We need to perform this operation for all leaf nodes and sum their decimal values to achieve our final answer.

The complexity of the problem arises from having to efficiently traverse the tree, convert binary paths to decimal numbers, and aggregate the sum of these numbers without storing all individual path values simultaneously (since only the sum is needed and we want to manage space efficiently).

Intuition

To solve this problem, we employ Depth-First Search (DFS), a common tree traversal technique particularly useful for situations where we need to explore all possible paths from a root to its leaves.

The essence of the solution lies in maintaining an ongoing sum (denoted as t in the code) as we traverse the tree. At each node, we shift the current sum one bit to the left (equivalent to multiplying the current total by 2 in binary) and add the current node's value.

The DFS function recurses with the updated sum t, and when a leaf node is encountered, this sum represents the decimal value of the path from the root to this leaf. If the node is a leaf (i.e., it has no children), we return the current sum t. Otherwise, we continue DFS on any existing children. The results from these recursive calls (representing the sums of each subtree's paths) are added together to form the cumulative total for larger subtrees.

By initiating this DFS from the root with an initial sum of 0, we ensure that all root-to-leaf paths are explored, their values are calculated in their binary to decimal form, and their sums are combined to produce the final total sum of all paths, which is returned at the end of the DFS function.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution provided uses a recursive Depth-First Search (DFS) strategy to traverse the tree. In DFS, we visit a node and recursively go deeper into each of the subtrees before coming back to explore other branches or nodes. This is particularly efficient for our purpose here because it allows us to construct the binary number represented by the path from the root to each leaf as we traverse the tree.

The main functions and patterns used in this approach are:

  • A Recursive Helper Function: dfs is a helper function which takes two parameters: root, representing the current node of the tree, and t, representing the ongoing path's sum in decimal form.
  • Bitwise Operations:
    • Left-Shift Operator <<: At each step, t is left-shifted by one bit to make space for the next digit. In binary, this is equivalent to t * 2.
    • Bitwise OR Operator |: After shifting t, the current node's value is added using the bitwise OR operator, which in this case simply appends the binary digit (0 or 1) at the least significant bit's position. This is due to 0 | 0 == 0, 0 | 1 == 1, 1 | 0 == 1, and 1 | 1 == 1.

The recursive process involves:

  1. Base Case: If the current node is None, the recursion stops and returns 0, as there's no number to add in an empty tree.
  2. Recursive Case: If the node is not empty, we calculate the ongoing sum t by left-shifting one bit and adding the node's value.
  3. Leaf Check: If the current node is a leaf (has no left or right subtree), the current accumulated sum t represents a complete path's number and is returned.
  4. Summation: If the current node isn't a leaf, we recursively call dfs for both the left and right children (if they exist) and add their returned values to get the sum for the current subtree rooted at root.

The initial call to dfs starts with the root of the tree and an initial sum of 0. As dfs gets called recursively, the sum t builds up to represent the number formed by the path from the root to the current node. When it reaches a leaf node, that number gets added to the total sum.

The solution's beauty lies in its elegant adding up of all the root-to-leaf path sums without explicitly storing each path's binary string, significantly optimizing both time and space complexity. This approach ensures that the solution is efficient and the algorithm can handle trees where the resulting sum fits within the bounds of a 32-bit integer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's take a simple example where our binary tree looks like this:

1    1
2   / \
3  0   1
4 / \
51   0

In this binary tree, there are three leaf nodes. To find the sum of all numbers formed by paths from the root to each leaf, we will calculate the binary number for each path, convert it to decimal and sum them up.

Step-by-Step Process:

  1. Start at the root node (value = 1). Initialize the ongoing sum t = 0.
  2. For the root node, calculate t = t * 2 + node_value. So initially, t = 0 * 2 + 1 = 1.
  3. Move to the left child (value = 0).
    • t = t * 2 + node_value becomes t = 1 * 2 + 0 = 2.
  4. Move to the left leaf (value = 1).
    • t = t * 2 + node_value becomes t = 2 * 2 + 1 = 5. This is the decimal value of the path '101', which is 5.
    • Since it's a leaf, add 5 to the sum.
  5. Move back and go to the right child of node 0 (value = 0, ignoring for now as it's non-leaf).
    • The previous path sum t was 2 before reaching left leaf, now t = 2 * 2 + 0 = 4. This is for path '100'.
    • Since it's a leaf, add 4 to the sum.
  6. The total sum is now 5 + 4 = 9. Now retreat to the root and go to the right child (value = 1).
    • At the root, t was 1. Now, t = 1 * 2 + 1 = 3.
  7. Move to the right leaf (value = 1).
    • t = t * 2 + node_value becomes t = 3 * 2 + 1 = 7. This is the decimal value of the path '11', which is 3.
    • Since it's a leaf, add 7 to the sum.

The total sum of the paths is now 9 (sum from the left subtree) + 7 = 16.

This is how the DFS algorithm works to compute the sum of all the numbers formed by the paths from the root to the leaves. The final answer for this example tree is 16.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def sumRootToLeaf(self, root: TreeNode) -> int:
10        # Helper function to perform depth-first search
11        def dfs(node, current_total):
12            # If the current node is None, we have reached a leaf or the tree is empty
13            if node is None:
14                return 0
15            # Add the current node's value to the running total by shifting
16            # the current total left (binary left shift) and OR with node's value
17            current_total = (current_total << 1) | node.val
18            # Check if the current node is a leaf node
19            if node.left is None and node.right is None:
20                # Return the current total for this root-to-leaf path
21                return current_total
22            # Otherwise, recursively call dfs for left and right subtrees and sum their values
23            return dfs(node.left, current_total) + dfs(node.right, current_total)
24
25        # Start the depth-first search with the root node and an initial total of 0
26        return dfs(root, 0)
27
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val; // The value of the node
6    TreeNode left; // Left child
7    TreeNode right; // Right child
8  
9    // Default constructor
10    TreeNode() {}
11  
12    // Constructor with value
13    TreeNode(int val) { this.val = val; }
14  
15    // Constructor with value, left, and right child
16    TreeNode(int val, TreeNode left, TreeNode right) {
17        this.val = val;
18        this.left = left;
19        this.right = right;
20    }
21}
22
23class Solution {
24    /**
25     * Public method to start the process of summing paths from root to leaves in a binary tree.
26     * @param root The root node of the binary tree.
27     * @return The total sum of all paths from root to leaves.
28     */
29    public int sumRootToLeaf(TreeNode root) {
30        return depthFirstSearch(root, 0);
31    }
32
33    /**
34     * Helper method to perform a depth-first search to calculate the sum of paths.
35     * It accumulates the binary numbers represented by the paths from the root to leaf nodes.
36     * @param node The current TreeNode being processed.
37     * @param currentSum The sum accumulated from the root to the current node.
38     * @return The sum of all leaf paths in the subtree rooted at the given node.
39     */
40    private int depthFirstSearch(TreeNode node, int currentSum) {
41        // Base condition - if the current node is null, return 0.
42        if (node == null) {
43            return 0;
44        }
45
46        // Left-shift the current sum to make space for the current node's value,
47        // and then add the current node's value using bitwise OR.
48        currentSum = (currentSum << 1) | node.val;
49
50        // If the node is a leaf node, return the current sum.
51        if (node.left == null && node.right == null) {
52            return currentSum;
53        }
54
55        // Recursively calculate the sum of the left and right subtrees,
56        // and return the total.
57        return depthFirstSearch(node.left, currentSum) + depthFirstSearch(node.right, currentSum);
58    }
59}
60
1/**
2 * Definition for a binary tree node structure.
3 */
4struct TreeNode {
5    int val;            // Value of the node
6    TreeNode *left;     // Pointer to left child
7    TreeNode *right;    // Pointer to right child
8    // Constructor to initialize with default values
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    // Constructor to initialize with a given value and null children
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    // Constructor to initialize with a value and left and right children
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16/**
17 * Solution class contains methods to solve the problem.
18 */
19class Solution {
20public:
21    // Public method that initiates the DFS traversal of the tree
22    int sumRootToLeaf(TreeNode* root) {
23        return depthFirstSearch(root, 0);
24    }
25
26private:
27    // Helper method using Depth-First Search to find the sum of all root-to-leaf numbers
28    // @param root: the current node
29    // @param currentSum: the sum computed so far from the root to this node
30    // @return: the sum of the root-to-leaf numbers
31    int depthFirstSearch(TreeNode* node, int currentSum) {
32        // base case: if the current node is null, return 0
33        if (!node) return 0;
34
35        // Shift current sum left and add current node's value to it
36        currentSum = (currentSum << 1) | node->val;
37
38        // If we're at a leaf node, return the current sum
39        if (!node->left && !node->right) return currentSum;
40
41        // Recursively compute the sum for left and right children and return their sum
42        return depthFirstSearch(node->left, currentSum) + depthFirstSearch(node->right, currentSum);
43    }
44};
45
1// Type definition for a binary tree node.
2type TreeNode = {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6};
7
8/**
9 * Calculates the sum of all root-to-leaf binary numbers in a binary tree.
10 * @param {TreeNode | null} root - The root node of the binary tree.
11 * @return {number} - The sum of all root-to-leaf numbers.
12 */
13function sumRootToLeaf(root: TreeNode | null): number {
14  /**
15   * Depth-first search helper function to traverse the tree and calculate binary numbers.
16   * @param {TreeNode | null} node - Current node in the binary tree.
17   * @param {number} currentNumber - The binary number formed from the root to the current node.
18   * @return {number} - The sum of root-to-leaf binary numbers starting from this node.
19   */
20  function depthFirstSearch(node: TreeNode | null, currentNumber: number): number {
21    if (node === null) {
22      return 0;
23    }
24
25    // Update the binary number by shifting left and adding the current node's value.
26    currentNumber = (currentNumber << 1) | node.val;
27
28    // If we are at a leaf node, return the current binary number as it represents a root-to-leaf path.
29    if (node.left === null && node.right === null) {
30      return currentNumber;
31    }
32
33    // Recursively call the depthFirstSearch on the left and right children, and return their sum.
34    return depthFirstSearch(node.left, currentNumber) + depthFirstSearch(node.right, currentNumber);
35  }
36
37  // Initialize the sum from the root node with 0 as the initial binary number.
38  return depthFirstSearch(root, 0);
39}
40
Not Sure What to Study? Take the 2-min Quiz๏ผš

Depth first search is equivalent to which of the tree traversal order?

Time and Space Complexity

The code provided is a depth-first search (DFS) algorithm on a binary tree that calculates the sum of root-to-leaf numbers represented as binary numbers.

Time Complexity

The time complexity of the DFS algorithm is O(N), where N is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once. During each visit, a constant amount of work is done: updating the current total t, and checking if the node is a leaf.

Therefore, the time complexity is O(N).

Space Complexity

The core of the space complexity analysis lies in the stack space taken up by the depth of the recursive calls. In the worst case, for a skewed tree (where each node has only one child), the maximum depth of the recursive call stack would be O(N).

However, in the best case, where the tree is perfectly balanced, the height of the tree would be O(log N), leading to a best-case space complexity of O(log N) due to the call stack.

Thus, the space complexity of the code can be expressed as O(h) where h is the height of the tree, which ranges from O(log N) (best case for a balanced tree) to O(N) (worst case for a skewed tree).

So, the space complexity is O(h).

Note: The space complexity does not consider the output since it is only an integer, which takes constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ