GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm


Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 – 1 – 1 – 0 – 1, then this could represent 01101 in binary, which is 13. For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

binary-tree-binary-numbers GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm algorithms DFS Go Programming

binary-tree-binary-numbers

Example 1:
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:
The number of nodes in the tree is between 1 and 1000.
node.val is 0 or 1.
The answer will not exceed 2^31 – 1.

GoLang Depth First Search Algorithm to Compute the Root to Leaves Binary Numbers

We need a helper Depth First Search function to compute the sum from current root to the leaves. Additionally, it needs to pass down a current sum up to now – which can be multiplied by two when passing down to the leaves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    return dfs(root, 0)
}
 
func dfs(root *TreeNode, cur int) int {
    if root == nil {
        return 0
    }    
    if root.Left == nil && root.Right == nil {
        return cur << 1 + root.Val
    }
    var a = dfs(root.Left, cur << 1 + root.Val) 
    var b = dfs(root.Right, cur << 1 + root.Val)
    return a + b
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(root *TreeNode, cur int) int {
    if root == nil {
        return 0
    }    
    if root.Left == nil && root.Right == nil {
        return cur << 1 + root.Val
    }
    var a = dfs(root.Left, cur << 1 + root.Val) 
    var b = dfs(root.Right, cur << 1 + root.Val)
    return a + b
}

Other root to leaves sum:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
459 words
Last Post: Teaching Kids Programming - Top Down Dynamic Programming Algorithm to Compute the Min Number of Knight Moves
Next Post: Teaching Kids Programming - Maximum Number by Inserting Five

The Permanent URL is: GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm

Leave a Reply