Binary Tree Paths Solution

Leetcode Solution: Understand and solve Leetcode problem Binary Tree Paths(257)

13 September 2020

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

		
				
Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

       1
     /   \
    2     3
     \
      5
    
    Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Return the sum of these numbers.

To solve this problem, we’ve to traverse all the leaf nodes and print the path to those leaf nodes. This means that the leaf node must be knowing about the path to itself from the root so that it can print it. We’ll be using the following tree as the example input for the problem:

We’ll start the traversal from the root with a blank array. Whenever we reach to a node, we’ll append it’s value into the array and pass the array to the child elements. This way once we reach a leaf node, we’ll be having the list of all those nodes that are in the path between the leaf node and the root node.

Finally, at the leaf node, we’re just joining that array with -> string.

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
}

var paths []string
func binaryTreePaths(root *TreeNode) []string {
	paths = make([]string, 0)
	if root == nil {
		return paths
	}
	var elements []string
	preOrder(root, elements)
	return paths

}

func preOrder(node *TreeNode, elements []string) {
	if node != nil {
		elements = append(elements, strconv.Itoa(node.Val))
	}
	if node.Left != nil {
		preOrder(node.Left, elements)
	}
	if node.Right != nil {
		preOrder(node.Right, elements)
	}
	if node.Left == nil && node.Right == nil {
		paths = append(paths, strings.Join(elements[:], "->"))
	}
}

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

Binary Tree Paths Solution

Leetcode Solution: Understand and solve Leetcode problem Binary Tree Paths(257)

Related Pages: