Sum of Root To Leaf Binary Numbers Solution in C++

Problem Description

Welcome to the whimsical world of binary trees, where every leaf is a potential goldmine of binary numbers! The problem at hand, “Sum of Root To Leaf Binary Numbers,” is like trying to find the total amount of candy in a tree made of candy canes. Each root-to-leaf path represents a binary number, and your job is to sum them all up.

Imagine you’re on a treasure hunt, and each path you take from the root to a leaf gives you a different treasure (in binary form, of course). But instead of gold coins, you get binary numbers! So, if you’re feeling adventurous and want to know how many binary treasures you’ve collected, this problem is for you.

Code Solution

Here’s the C++ solution that will help you gather all those binary treasures:

Copy Code

class Solution {
 public:
  int sumRootToLeaf(TreeNode* root) {
    int ans = 0;
    dfs(root, 0, ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, int val, int& ans) {
    if (root == nullptr)
      return;
    val = val * 2 + root->val;
    if (root->left == nullptr && root->right == nullptr)
      ans += val;
    dfs(root->left, val, ans);
    dfs(root->right, val, ans);
  }
};

Approach

The approach here is as straightforward as pie (or should I say binary pie?). We perform a depth-first search (DFS) on the binary tree. As we traverse from the root to each leaf, we build the binary number by shifting the current value left (multiplying by 2) and adding the current node’s value. When we reach a leaf node, we add the constructed binary number to our answer. Simple, right?

Time and Space 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 is due to the recursion stack.

Real-World Example

Think of a family tree where each family member has a unique binary number representing their lineage. As you trace your ancestry from the root (great-grandparents) down to the leaves (you and your siblings), you collect all the binary numbers associated with each path. By the end of your journey, you sum up all these numbers to find out how rich your family history is in binary terms!