Binary Tree Most Path Sum Program in Go (Golang)

A  binary tree is given. The target is to search out the utmost Path Sum in that binary tree.  A path in a binary tree is a sequence of nodes which might be related to one another. Every node solely seems as soon as within the Most Path Sum

Instance 1

Output: 16
Most Sum Path is: 4->2->1->3->6

Instance 2

Output: 14
Most Sum Path is: 5->3->6

The concept is to trace beneath 4  values at each node

• b = root.Val + leftSubTreeMaxSum

• c  = root.Val + rightSubTreeMaxSum

• d =  root.Val + leftSubTreeMaxSum+  rightSubTreeMaxSum

Then

• Max sum at a given node is given max of (a,b,c,d)

• The return worth within the recursive name can be a max of (a,b,c).  Why? It’s because solely the trail of a or b or c represents a path that may be taken into consideration on the guardian node. d can’t be taken into consideration as a result of it turns into an invalid path. To know this with an instance think about the binary tree in instance two above. Path 5->3->6 can’t embody guardian node -5 in its path as a result of it turns into an invalid path.

Under is this system for a similar

bundle foremost

import (
	"fmt"
	"math"
)

kind TreeNode struct {
	Val   int
	Left  *TreeNode
	Proper *TreeNode
}

func maxPathSum(root *TreeNode) int {
	res := math.MinInt64

	maxPathSumUtil(root, &res)
	return res
}

func maxPathSumUtil(root *TreeNode, res *int) int {
	if root == nil {
		return 0
	}

	l := maxPathSumUtil(root.Left, res)
	r := maxPathSumUtil(root.Proper, res)

	a := root.Val
	b := root.Val + l
	c := root.Val + r
	d := root.Val + l + r

	maxReturnSum := maxOfThree(a, b, c)

	maxSumPath := maxOfTwo(maxReturnSum, d)
	if maxSumPath > *res {
		*res = maxSumPath
	}

	return maxReturnSum
}

func maxOfThree(a, b, c int) int {
	if a > b && a > c {
		return a
	}

	if b > c {
		return b
	}

	return c
}

func maxOfTwo(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func foremost() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Left.Left = &TreeNode{Val: 4}
	root.Proper = &TreeNode{Val: 3}
	root.Proper.Left = &TreeNode{Val: 5}
	root.Proper.Proper = &TreeNode{Val: 6}

	output := maxPathSum(root)
	fmt.Println(output)

	root = &TreeNode{Val: -10}
	root.Left = &TreeNode{Val: 2}
	root.Left.Left = &TreeNode{Val: 4}
	root.Proper = &TreeNode{Val: 3}
	root.Proper.Left = &TreeNode{Val: 5}
	root.Proper.Proper = &TreeNode{Val: 6}
	output = maxPathSum(root)
	fmt.Println(output)

}

Output:

16
14

Word: Try our Golang Superior Tutorial. The tutorials on this sequence are elaborative and we now have tried to cowl all ideas with examples. This tutorial is for many who wish to achieve experience and a stable understanding of golang – Golang Advance Tutorial

Additionally in case you are excited about understanding how all design patterns will be applied in Golang. If sure, then this publish is for you – All Design Patterns Golang

Additionally, take a look at our system design tutorial sequence right here – System Design Tutorial Collection