Go: check if a binary tree is symmetric

A binary tree is a common data structure in computer science used to organize data into a tree structure. One of the interesting aspects of binary trees is their symmetry. A binary tree is considered symmetric when the left subtree of each node is a mirror image of the right subtree with respect to the root. In this article, we will explore how to check whether a binary tree is symmetric using the Go programming language.

Representation of a Binary Tree in Go

Before you start testing the symmetry of a binary tree, it is important to understand how to represent a binary tree in Go. One of the common representations is to use a structure with fields for the node value, the left subtree, and the right subtree. Here's what this structure might look like:

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

Each node contains a value (usually an integer) and two pointers representing the left and right subtrees. Now that we have a representation of the binary tree, we can proceed with the symmetry check.

Checking the Symmetry of a Binary Tree

Checking the symmetry of a binary tree can be done using a depth-first search of the tree. The main idea is to compare the left subtree of a node with the right subtree of the corresponding node. If both subtrees are null or if the corresponding node values are equal and the left and right subtrees are symmetric, the tree is symmetric.

Here is a Go function that checks the symmetry of a binary tree:

func isSymmetric(root *TreeNode) bool {
     if root == nil {
         return true // An empty tree is symmetric
     }
     return isMirror(root.Left, root.Right)
}

func isMirror(left *TreeNode, right *TreeNode) bool {
     if left == nil && right == nil {
         return true // Both subtrees are empty, so they are symmetric
     }
     if left == nil || right == nil {
         return false // Only one of the subtrees is empty, so they are not symmetric
     }
     return (left.Val == right.Val) &&
         isMirror(left.Left, right.Right) &&
         isMirror(left.Right, right.Left)
}

The isSymmetric function checks whether the binary tree passed as an argument is symmetric. The auxiliary function isMirror checks the symmetry of the left and right subtrees of a node. This recursive approach examines all nodes of the tree and returns true if the tree is symmetric, otherwise it returns false.

Here is an example of how to use the isSymmetric function with a binary tree:

func main() {
     // Create a symmetric binary tree
     root := &TreeNode{Val: 1}
     root.Left = &TreeNode{Val: 2}
     root.Right = &TreeNode{Val: 2}
     root.Left.Left = &TreeNode{Val: 3}
     root.Left.Right = &TreeNode{Val: 4}
     root.Right.Left = &TreeNode{Val: 4}
     root.Right.Right = &TreeNode{Val: 3}

     isSymmetric := isSymmetric(root)
     if isSymmetric {
         fmt.Println("The tree is symmetric.")
     } else {
         fmt.Println("The tree is not symmetric.")
     }
}

In this example, the created binary tree is symmetric, and therefore the program will print "The tree is symmetric."

You now have a solid understanding of how to check the symmetry of a binary tree using the Go programming language. You can apply this concept to solve problems involving symmetric binary trees in real-world situations.