A Collection of tree algorithms and important questions

trees.go

package main

import "fmt"

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

// 1. Maximum Depth of Binary Tree
func maxDepth(root *TreeNode) {
	fmt.Println("Max Depth:", dfsMaxDepth(root))
}

func dfsMaxDepth(node *TreeNode) int {
	if node == nil {
		return 0
	}
	left := dfsMaxDepth(node.Left)
	right := dfsMaxDepth(node.Right)
	if left > right {
		return left + 1
	}
	return right + 1
}

// 2. Invert (Mirror) Binary Tree
func invertTree(root *TreeNode) {
	dfsInvert(root)
	fmt.Print("Inverted Tree (Preorder): ")
	printPreOrder(root)
	fmt.Println()
}

func dfsInvert(node *TreeNode) *TreeNode {
	if node == nil {
		return nil
	}
	node.Left, node.Right = dfsInvert(node.Right), dfsInvert(node.Left)
	return node
}

// 3. Same Tree
func isSameTree(p, q *TreeNode) {
	fmt.Println("Is Same Tree:", dfsSame(p, q))
}

func dfsSame(p, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil || p.Val != q.Val {
		return false
	}
	return dfsSame(p.Left, q.Left) && dfsSame(p.Right, q.Right)
}

// 4. Diameter of Binary Tree
func diameterOfBinaryTree(root *TreeNode) {
	maxDiameter := 0
	_ = dfsDiameter(root, &maxDiameter)
	fmt.Println("Diameter:", maxDiameter)
}

func dfsDiameter(node *TreeNode, maxDia *int) int {
	if node == nil {
		return 0
	}
	left := dfsDiameter(node.Left, maxDia)
	right := dfsDiameter(node.Right, maxDia)
	*maxDia = max(*maxDia, left+right)
	if left > right {
		return left + 1
	}
	return right + 1
}

// 5. Path Sum (Root to Leaf Sum)
func hasPathSum(root *TreeNode, targetSum int) {
	fmt.Println("Has Path Sum:", dfsPathSum(root, targetSum))
}

func dfsPathSum(node *TreeNode, sum int) bool {
	if node == nil {
		return false
	}
	if node.Left == nil && node.Right == nil {
		return node.Val == sum
	}
	sum -= node.Val
	return dfsPathSum(node.Left, sum) || dfsPathSum(node.Right, sum)
}

// Build sample binary tree
func buildTree() *TreeNode {
	return &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val:   2,
			Left:  &TreeNode{Val: 4},
			Right: &TreeNode{Val: 5},
		},
		Right: &TreeNode{
			Val:   3,
			Left:  &TreeNode{Val: 6},
			Right: &TreeNode{Val: 7},
		},
	}
}

// Preorder Print
func printPreOrder(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Print(root.Val, " ")
	printPreOrder(root.Left)
	printPreOrder(root.Right)
}


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

func main() {
	tree := buildTree()

	maxDepth(tree)

	invertTree(tree)

	tree2 := buildTree()
	isSameTree(tree, tree2) 

	diameterOfBinaryTree(tree)

	hasPathSum(tree, 8)  // true: 1 -> 2 -> 5
	hasPathSum(tree, 27) // false
}