A binary tree is a tree data structure where each node has at most two children, referred to as the left child and right child. Structure 1type TreeNode struct { 2 Val int 3 Left *TreeNode 4 Right *TreeNode 5} 6 7// Helper to create a node 8func NewNode(val int) *TreeNode { 9 return &TreeNode{Val: val} 10} …