The blog for Design Patterns, Linux, HA and Myself!

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...

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode