Sum of Root To Leaf Binary Numbers

easy binary tree dfs bit manipulation

Problem

You are given the root of a binary tree where every node has value 0 or 1. Each root-to-leaf path represents a binary number, read from the most significant bit at the root to the least significant bit at the leaf. Return the sum of these numbers for all leaves.

Inputroot = [1, 0, 1, 0, 1, 0, 1]

Output22

Paths read as binary: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22.

tree (level-order, comma-separated, use null)

def sum_root_to_leaf(root):
    def dfs(node, cur):
        if node is None:
            return 0
        cur = (cur << 1) | node.val
        if node.left is None and node.right is None:
            return cur
        return dfs(node.left, cur) + dfs(node.right, cur)
    return dfs(root, 0)

function sumRootToLeaf(root) {
  function dfs(node, cur) {
    if (node === null) return 0;
    cur = (cur << 1) | node.val;
    if (node.left === null && node.right === null) return cur;
    return dfs(node.left, cur) + dfs(node.right, cur);
  }
  return dfs(root, 0);
}

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int cur) {
        if (node == null) return 0;
        cur = (cur << 1) | node.val;
        if (node.left == null && node.right == null) return cur;
        return dfs(node.left, cur) + dfs(node.right, cur);
    }
}

int dfs(TreeNode* node, int cur) {
    if (node == nullptr) return 0;
    cur = (cur << 1) | node->val;
    if (node->left == nullptr && node->right == nullptr) return cur;
    return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumRootToLeaf(TreeNode* root) {
    return dfs(root, 0);
}

Explanation

Each path from the root down to a leaf spells out a binary number, with the root as the highest bit. We want the sum of all those numbers, and we build each one as we walk down the tree.

The helper dfs(node, cur) carries cur, the number formed so far. At every node we do cur = (cur << 1) | node.val. The left shift << 1 moves the existing bits up one place (multiply by two), and the or | node.val tacks the new bit onto the end.

When we reach a leaf, cur holds the complete binary number for that path, so we return it. Otherwise we recurse into both children and add their results, which sums up every root-to-leaf path.

Example: [1,0,1,0,1,0,1]. The four paths read as 100, 101, 110, 111, i.e. 4 + 5 + 6 + 7 = 22. Following the leftmost path, cur goes 1 then 10 then 100 = 4.

We touch each node once, so the algorithm runs in O(n) time.

Time: O(n) Space: O(h)