Sum of Root To Leaf Binary Numbers Solution in Java

Language Options

Problem Description

The “Sum of Root To Leaf Binary Numbers” problem involves traversing a binary tree from the root to each leaf, forming binary numbers along the way. Your task is to sum up all those binary numbers. Imagine you’re on a road trip, collecting snacks at each rest stop; here, instead of snacks, we collect binary values!

Code Solution


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

  private int ans = 0;

  private void dfs(TreeNode root, int val) {
    if (root == null)
      return;
    val = val * 2 + root.val;
    if (root.left == null && root.right == null)
      ans += val;
    dfs(root.left, val);
    dfs(root.right, val);
  }
}

Approach Explanation

The code uses a depth-first search (DFS) approach to traverse the binary tree. Starting from the root, it keeps track of the current binary value (val) as it moves down the tree. When it reaches a leaf node, it adds the binary value to the total sum (ans). The binary value is calculated by shifting the previous value left (multiplying by 2) and adding the current node’s value.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of nodes in the tree.
Space Complexity	O(H), where H is the height of the tree.

Real-World Example

Imagine you’re on a treasure hunt in a park shaped like a binary tree. Each path you take (left or right) leads you to a treasure chest (leaf node) filled with binary coins. The value of each chest is determined by the path you took to get there. By the end of your adventure, you want to know the total value of all the treasures you’ve collected. That’s exactly what this problem is about!