algoadvance

Leetcode 1022. Sum of Root To Leaf Binary Numbers

Problem Statement

Given a binary tree where each node contains a single digit (0 or 1), each path from the root to a leaf represents a binary number. You need to find the sum of these binary numbers represented by all paths from the root to the leaves.

Clarifying Questions

  1. What is a root-to-leaf path?
    • A path that starts from the root node and ends at a leaf node (a node with no children).
  2. What should be the format of the output?
    • The output should be an integer which is the sum of all the binary numbers represented by root-to-leaf paths.
  3. Are there any constraints on the size of the tree?
    • The number of nodes in the tree is in the range [1, 1000].
    • Node values are either 0 or 1.

Code

Here is the Java code to solve the problem:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

Strategy

  1. Depth-First Search (DFS):
    • Traverse the tree using DFS which can be implemented using recursion.
  2. Bit Manipulation:
    • To construct the binary number, use bitwise operations.
    • Shift currentSum to the left by 1 bit (currentSum << 1), then add the value of the current node (node.val).
  3. Base Case:
    • If the current node is null, return 0 since it does not contribute to any path.
  4. Leaf Node:
    • If both children of the current node are null, it means we have reached a leaf node. Return the currentSum.
  5. Recursive Case:
    • Recursively call the dfs method on the left and right children of the current node.
    • Sum the results of the left and right recursive calls to get the total sum for the current path.

Time Complexity

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