Problem of The Day: Sum of Root To Leaf Binary Numbers

2 min read 598 words

Problem Statement

leetcode problem link

Solution [Accepted]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private double _result = 0;
    public void DFS(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            sb.Append(node.val);
            _result += Convert.ToInt32(sb.ToString(), 2);
            return ;
        }

        sb.Append(node.val);
        DFS(node.left, new StringBuilder(sb.ToString()));
        DFS(node.right, new StringBuilder(sb.ToString()));
    }

    public int SumRootToLeaf(TreeNode root) {
        DFS(root, new StringBuilder());
        return Convert.ToInt32(_result);
    }
}

Improve Algorithm

public class Solution
{
    public int SumRootToLeaf(TreeNode root)
    {
        return Dfs(root, 0);
    }

    private int Dfs(TreeNode node, int acc)
    {
        if (node == null) return 0;

        // Shift left (multiply by 2) and add current bit
        acc = (acc << 1) | (node.val & 1);

        // If leaf, return the accumulated value
        if (node.left == null && node.right == null)
            return acc;

        // Sum from left and right subtrees
        return Dfs(node.left, acc) + Dfs(node.right, acc);
    }
}

Editorial

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        root_to_leaf = 0
        stack = [(root, 0) ]

        while stack:
            root, curr_number = stack.pop()
            if root is not None:
                curr_number = (curr_number << 1) | root.val
                # if it's a leaf, update root-to-leaf sum
                if root.left is None and root.right is None:
                    root_to_leaf += curr_number
                else:
                    stack.append((root.right, curr_number))
                    stack.append((root.left, curr_number))

        return root_to_leaf