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

View this thread on steempeak.com
· @justyy ·
$27.52
GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm
<blockquote>
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"]<a href="https://helloacm.com/wp-content/uploads/2019/04/binary-tree-binary-numbers.jpg"><img src="https://helloacm.com/wp-content/uploads/2019/04/binary-tree-binary-numbers.jpg" alt="binary-tree-binary-numbers" width="738" height="486" class="size-full wp-image-6888" /></a> 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.
</blockquote>

<h3>GoLang Depth First Search Algorithm to Compute the Root to Leaves Binary Numbers</h3>
We need a helper <a href="https://helloacm.com/teaching-kids-programming-subtree-with-maximum-value-via-recursive-depth-first-search-algorithm/" title="Teaching Kids Programming – Subtree with Maximum Value via Recursive Depth First Search Algorithm">Depth First Search</a> 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 &lt;&lt; 1 + root.Val
    }
    var a = dfs(root.Left, cur &lt;&lt; 1 + root.Val) 
    var b = dfs(root.Right, cur &lt;&lt; 1 + root.Val)
    return a + b
}
```

Other root to leaves sum:
<ul>
<li><a target="_blank" href="https://helloacm.com/teaching-kids-programming-depth-first-search-algorithm-to-sum-the-root-to-leaf-numbers-in-binary-tree/" rel="noopener">Teaching Kids Programming - Depth First Search Algorithm to Sum the Root to Leaf Numbers in Binary Tree</a></li>
<li><a target="_blank" href="https://helloacm.com/how-to-sum-the-root-to-leaf-in-binary-numbers-in-a-binary-tree-using-breadth-first-search/" rel="noopener">How to Sum the Root To Leaf in Binary Numbers in a Binary Tree using Breadth First Search?</a></li>
<li><a target="_blank" href="https://helloacm.com/teaching-kids-programming-breadth-first-search-algorithm-to-sum-root-to-leaf-numbers-in-binary-tree/" rel="noopener">Teaching Kids Programming - Breadth First Search Algorithm to Sum Root to Leaf Numbers in Binary Tree</a></li>
<li><a href="https://helloacm.com/golang-sum-of-root-to-leaf-binary-numbers-via-depth-first-search-algorithm/" title="GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm">GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm</a></li>
</ul>

Reposted to [Blog](https://helloacm.com/golang-sum-of-root-to-leaf-binary-numbers-via-depth-first-search-algorithm/)

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Thank you for reading ^^^^^^^^^^^^^^^
---------------
## NEW! [Following my Trail (Upvote or/and Downvote)](https://steemit.com/witness-category/@justyy/following-my-trail-upvote-or-and-downvote-by-authorizing-posting-key-to-me)


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

#### My contributions
- [Video Downloader](https://weibomiaopai.com/download-video-parser.php)
- [Steem Blockchain Tools](https://steemyy.com)
- [Free Cryptos API](https://steemit.com/witness-category/@justyy/serverless-api-to-query-the-cryptos-and-fiat)
- [VPS Database](https://anothervps.com/vps-database/)
- [Computing Technology Blog](https://helloacm.com)
- [A few useless tools](https://helloacm.com/tools/)
- [And some other online software/tools](https://steakovercooked.com/Software.Home)
- [Merge Files/Videos](https://slowapi.com/merge-videos/)
- [LOGO Turtle Programming Chrome Extension](https://chrome.google.com/webstore/detail/logo-turtle-graphics/dcoeaobaokbccdcnadncifmconllpihp)
- [Teaching Kids Programming - Youtube Channel](https://www.youtube.com/channel/UCK2ugmUOoYne1qQfSAph4nQ?view_as=subscriber) and [All Contents](https://github.com/DoctorLai/Teaching-Kids-Programming/blob/main/README.md)

#### Delegation Service
1. [Voting Algorithm Updated to Favor those High Delegations!](https://steemit.com/wherein/@justyy/voting-algorithm-updated-to-favor-those-high-delegations)

- Delegate 1000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amp;amount=1000)
- Delegate 5000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amp;amount=5000)
- Delegate 10000 to justyy: [Link](https://steemyy.com/sp-delegate-form/?delegatee=justyy&amp;amount=10000)

#### Support me
If you like my work, please: 
- [Buy Me a Coffee](https://justyy.com/out/buymeacoffee), Thanks!
- [Become my Sponsor](https://github.com/sponsors/DoctorLai), Thanks!
- Voting for me:
https://steemit.com/~witnesses type in **justyy** and click ***VOTE***
https://steemyy.com/images/vote-for-justyy.jpg


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


-------------
👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 82 others
👎  
properties (23)
post_id91,871,304
authorjustyy
permlinkgolang-sum-of-root-to-leaf-binary-numbers-via-depth-first-search-algorithm
categoryprogramming
json_metadata{"tags":["programming","golang","sct","blog","whalepower","coding","upmefund","palnet"],"users":["justyy"],"image":["https:\/\/helloacm.com\/wp-content\/uploads\/2019\/04\/binary-tree-binary-numbers.jpg","https:\/\/steemyy.com\/images\/vote-for-justyy.jpg"],"links":["https:\/\/helloacm.com\/wp-content\/uploads\/2019\/04\/binary-tree-binary-numbers.jpg","https:\/\/helloacm.com\/teaching-kids-programming-subtree-with-maximum-value-via-recursive-depth-first-search-algorithm\/","https:\/\/helloacm.com\/teaching-kids-programming-depth-first-search-algorithm-to-sum-the-root-to-leaf-numbers-in-binary-tree\/","https:\/\/helloacm.com\/how-to-sum-the-root-to-leaf-in-binary-numbers-in-a-binary-tree-using-breadth-first-search\/","https:\/\/helloacm.com\/teaching-kids-programming-breadth-first-search-algorithm-to-sum-root-to-leaf-numbers-in-binary-tree\/","https:\/\/helloacm.com\/golang-sum-of-root-to-leaf-binary-numbers-via-depth-first-search-algorithm\/","https:\/\/steemit.com\/witness-category\/@justyy\/following-my-trail-upvote-or-and-downvote-by-authorizing-posting-key-to-me","https:\/\/steemyy.com","https:\/\/weibomiaopai.com\/download-video-parser.php","https:\/\/steemit.com\/witness-category\/@justyy\/serverless-api-to-query-the-cryptos-and-fiat","https:\/\/anothervps.com\/vps-database\/","https:\/\/helloacm.com","https:\/\/helloacm.com\/tools\/","https:\/\/steakovercooked.com\/Software.Home","https:\/\/slowapi.com\/merge-videos\/","https:\/\/chrome.google.com\/webstore\/detail\/logo-turtle-graphics\/dcoeaobaokbccdcnadncifmconllpihp","https:\/\/www.youtube.com\/channel\/UCK2ugmUOoYne1qQfSAph4nQ?view_as=subscriber","https:\/\/github.com\/DoctorLai\/Teaching-Kids-Programming\/blob\/main\/README.md","https:\/\/steemit.com\/wherein\/@justyy\/voting-algorithm-updated-to-favor-those-high-delegations","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amp;amount=1000","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amp;amount=5000","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy&amp;amount=10000","https:\/\/justyy.com\/out\/buymeacoffee","https:\/\/github.com\/sponsors\/DoctorLai","https:\/\/steemit.com\/~witnesses","https:\/\/steemyy.com\/sp-delegate-form\/?delegatee=justyy","https:\/\/steemyy.com\/witness-voting\/?witness=justyy&amp;action=approve","https:\/\/steemyy.com\/witness-voting\/?witness=justyy&amp;action=proxy"],"app":"steemit\/0.2","format":"markdown"}
created2021-06-11 09:53:06
last_update2021-06-11 09:53:06
depth0
children3
net_rshares35,622,408,268,552
last_payout2021-06-18 09:53:06
cashout_time1969-12-31 23:59:59
total_payout_value14.032 SBD
curator_payout_value13.487 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length5,859
author_reputation1,990,164,104,714,661
root_title"GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
author_curate_reward""
vote details (147)
@tomoyan ·
Upvote not working today?
properties (22)
post_id91,882,578
authortomoyan
permlinkqujy2z
categoryprogramming
json_metadata{"app":"steemit\/0.2"}
created2021-06-11 19:28:12
last_update2021-06-11 19:28:12
depth1
children1
net_rshares0
last_payout2021-06-18 19:28:12
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length25
author_reputation842,472,154,758,125
root_title"GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@justyy ·
fixed.
properties (22)
post_id91,884,020
authorjustyy
permlinkquk2vt
categoryprogramming
json_metadata{"app":"steemit\/0.2"}
created2021-06-11 21:11:54
last_update2021-06-11 21:11:54
depth2
children0
net_rshares0
last_payout2021-06-18 21:11:54
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length6
author_reputation1,990,164,104,714,661
root_title"GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@paulyoung ·
I don't know anything about programming about always feel curios to know.
Ago(2013), the person that pretended to teach me later scammed me and ran away with my tution fee.
But i believe that one day, I'll be know it because I'm not gonna give up.
Thank you sir for posting this
Much respect
properties (22)
post_id91,894,679
authorpaulyoung
permlinkqukz5d
categoryprogramming
json_metadata{"app":"steemit\/0.2"}
created2021-06-12 08:48:54
last_update2021-06-12 08:48:54
depth1
children0
net_rshares0
last_payout2021-06-19 08:48:54
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length291
author_reputation9,237,523,485,500
root_title"GoLang: Sum of Root To Leaf Binary Numbers via Depth First Search Algorithm"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000