Golang with Leetcode: Same Tree

Leetcode Problem #100: Same Tree Solution in Golang

src: Golang Gopher Go Six Pack — Golang — Sticker | TeePublic (not affiliated, just liked the picture)

Leetcode #100: Same Tree

Difficulty: Easy

Acceptance Rate: 55.3%

Problem Breakdown

This problem is essentially a graph traversal problem. The solution must symmetrically traverse the branches of each tree node provided and do a comparison if the values at the branches are equal.

Edge cases to consider are if both nodes are empty, then they are technically considered equal. Another edge case is to check if one node is empty and the other is not; this automatically tells us the branches are not equal.

Recursion provides a natural and intuitive solution to tree traversals, as it is common to implement in depth-first search and breadth-first search approaches. DFS and BFS are common graph traversal methods, however, this appears to be an introductory problem to graph traversals, so we are able to solve with a simple recursive solution for now.

Problem Solution:

The commented code above the isSameTree function is provided by Leetcode to let us know the structure of the TreeNode struct.

The first thing we will do is declare a variable to store the result of our operation. We will simply call this variable “result.” We will provide it a default value of false, as this saves us from writing multiple return statements, thereby improving our problem solving logic. After that, we check if both pointers are nil. You can see that if they are both nil, the result gets set to true. This is like we said earlier: if both pointers are both empty, then they are technically equal.

After the initial edge case, we then check to make sure both pointers are not nil before we do some more processing. If the pointers are not nil, we check if the values are equal. If they are, we recursively call the function and pass it the left and right pointers separately. This will allow our recursive call to traverse both paths and compare the equality between the corresponding branches of each node.

We then return the result

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    var result bool = false
    
    if p == nil && q == nil {
        result = true
    } else if p != nil && q != nil {
        if p.Val == q.Val {
            result = isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
        }
    }
    
    return result
}

Closing Remarks