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

in blurt •  6 days ago 
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.

[caption id="attachment_6888" align="alignnone" width="738"]binary-tree-binary-numbers binary-tree-binary-numbers[/caption]

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.

/**
 * 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:

Reposted to Blog

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Thank you for reading ^^^^^^^^^^^^^^^

NEW! Following my Trail (Upvote or/and Downvote)

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

My contributions

Delegation Service

  1. Voting Algorithm Updated to Favor those High Delegations!
  • Delegate 1000 to justyy: Link
  • Delegate 5000 to justyy: Link
  • Delegate 10000 to justyy: Link

Support me

If you like my work, please:

  1. Delegate SP: https://steemyy.com/sp-delegate-form/?delegatee=justyy
  2. Vote @justyy as Witness: https://steemyy.com/witness-voting/?witness=justyy&action=approve
  3. Set @justyy as Proxy: https://steemyy.com/witness-voting/?witness=justyy&action=proxy
    Alternatively, you can vote witness or set proxy here: https://steemit.com/~witnesses

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE BLURT!
Sort Order:  

Congratulations! This post has been upvoted by the @blurtcurator communal account,
You can request a vote every 12 hours from the #getupvote channel in the official Blurt Discord.Don't wait to join ,lots of good stuff happening there.

Congratulations, your post has been upvoted by @r2cornell, which is the curating account for @R2cornell's Discord Community.

Curated by <@bestkizito >

r2cornell_curation_banner.png