Sum of Root to Leaf Binary Numbers - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Sum of Root to Leaf Binary Numbers(1022)

30 August 2020

In this article, we’ll be solving the problem: Sum of Root To Leaf Binary Numbers. This problem belongs to Tree Traversal category and just like the problem, Maximum Depth of N Ary Tree, and Increasing Order Search Tree this problem also requires a slight modification in a simple Tree Traversal approach.

		
				
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.

Example 1:
                1
              /   \
             0     1
            / \   / \
           0   1 0   1   

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

Return the sum of these numbers.

Just like the other problems in this tag, this one also belongs to the Tree Traversal category. To solve this problem we need to know the path to each of the leaf nodes from the root of the tree. The path will actually contain the node value of the tree nodes which means that the path will only contain the binary representation of a decimal number.

Once we get the entire path to the node, we can then convert the binary string to the decimal number and then sum that number to totalSum because to solve it we have to return the sum of all the path values.

In this image the text with red font is the character that is appended to the path after the current node’s traversal is done. We start with 1, the root element, and the path becomes “1”. Then we traverse to the left node and that adds 0 to the path, “01”. Then we traverse to one of the leaf nodes and we calculate the sum.

Here is the code for the solution to this problem that can also be found here on GitHub as well.

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// sum will keep the sum of all the path
var sum int

func sumRootToLeaf(root *TreeNode) int {
	sum = 0
	preOrder(root, "0")
	return sum
}

// preOrder gets the node to traverse and the binary string found till now
func preOrder(node *TreeNode, binaryTillNow string) {
    // while traversing the node
    // we append the current node's value to the binaryTillNow string
    // and this value will be passed to all its child 
	binaryTillNow = binaryTillNow + strconv.Itoa(node.Val)
	if node.Left != nil {
		preOrder(node.Left, binaryTillNow)
	}
	if node.Right != nil {
		preOrder(node.Right, binaryTillNow)
	}
	if node.Left == nil && node.Right == nil {
	    // if the node is a leaf node
        // we convert the binary to integer
		i, _ := strconv.ParseInt(binaryTillNow, 2, 64)
        // and add that value to the sum variable
		sum += int(i)
	}
}

The sum variable keeps the sum of all the paths. We’re using Itoa to convert the integer to string and ParseInt to convert the binary string to an integer.

Loading Comments... Disqus Loader

Sum of Root to Leaf Binary Numbers - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Sum of Root to Leaf Binary Numbers(1022)

Related Pages: