algoadvance

Leetcode 1022. Sum of Root To Leaf Binary Numbers

Problem Statement

Given a binary tree containing 0s and 1s, each root-to-leaf path represents a binary number starting with the root. For example, if the path is 0 -> 1 -> 1 -> 0, then the binary number is 0110, which is 6 in decimal. Return the sum of these numbers computed for all such paths in the tree.

Clarifying Questions

1. What is the structure of the tree node?
   • The tree node has int val for the value (0 or 1), and pointers TreeNode* left and TreeNode* right for its children.
2. What is the range of the number of nodes in the tree?
   • The number of nodes ranges from 1 to 1000.
3. Is the tree guaranteed to be valid and well-formed (no cycles)?
   • Yes, it’s a valid binary tree with no cycles.
4. What should we return if the tree is empty?
   • Given the constraints, we can assume the tree is never empty.

Code

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int currentSum) {
        if (!node) return 0;
        
        currentSum = (currentSum << 1) | node->val;
        
        // If it's a leaf node, return the current accumulated sum
        if (!node->left && !node->right) {
            return currentSum;
        }
        
        // Otherwise, continue the DFS on both subtrees
        return dfs(node->left, currentSum) + dfs(node->right, currentSum);
    }
};

Strategy

1. Depth-First Search (DFS):
   • We’ll use DFS to traverse the tree from the root to each leaf.
   • For each node, we update the current binary sum by shifting left by 1 bit (currentSum << 1) and adding the node’s value (using binary OR | node->val).
2. Leaf Node Check:
   • Once a leaf node is reached (both left and right are nullptr), we add the accumulated binary sum to the total sum.
3. Recursive Traversal:
   • Apply the same process recursively for both left and right subtrees.
   • Sum the values obtained from the left and right subtrees and return the result.

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(h), where h is the height of the tree. This accounts for the recursion stack during the DFS traversal. In the worst case (a completely unbalanced tree), h could be n. In the best case (a balanced tree), h would be log(n).

With the above approach, we can efficiently compute the sum of all root-to-leaf binary numbers in the given binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?