Solution to Leetcode 1022: Sum of Root To Leaf Binary Numbers

In this Leetcode problem, we are asked to return the addition of all the value of paths from root to leaf where the value of a path is the path interpreted as a binary string.

Problem statement

The solution involves mostly a depth first search keeping track of the current integer represented by the binary string. For instance if the current value of the upstream path is x, the value represented at the given node n is 2*x+n.Val.

When we reach a leaf, we return the current value represented by the path. when we are not at a leaf, we add the value obtained from the left and the right recursion.

I added a little subroutine to check if a node is a leaf:

func isLeaf(node *TreeNode) bool {
    return node.Left == nil && node.Right == nil
}

In terms of complexity. O(N) for the DFS, and O(N) additions to compute the result. Here is the full code:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    return sumRootToLeafRec(root, 0)
}
func sumRootToLeafRec(root *TreeNode, current int) int {
    if root == nil {
        return 0
    }
    current = current << 1
    current += root.Val
    if isLeaf(root) {
        return current
    }
    return 
        sumRootToLeafRec(root.Left, current) 
        + sumRootToLeafRec(root.Right, current)
}
func isLeaf(node *TreeNode) bool {
    return node.Left == nil && node.Right == nil
}