Learning GoLang: Check Same Binary Trees via DFS or BFS Algorithms

justyy (84)in #programming • 5 years ago

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

GoLang: Same Tree Algorithm via Recursive Depth First Search Algorithm

Checking two binary trees for equality - we need to check two things: root values and their structures. The root values checking is easy - and we can do the recursion to check their structures - left and right trees.

The following is the Recursive Depth First Search Algorithm to check two binary trees for equality.

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

The time and space complexity is O(N) where N is the less number of the nodes in two binary trees i.e. O(Min(P, Q)). Using a Recursion implies the usage of Stack.

GoLang: Same Tree Algorithm via Breadth First Search Algorithm

We can also perform a Breadth First Search Algorithm via a queue - level-by-level order traversal.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    var Q = make([][]*TreeNode, 0)
    Q = append(Q, []*TreeNode{p, q})
    for len(Q) &gt; 0 {
        a, b := Q[0][0], Q[0][1]
        Q = Q[1:]
        if a == nil && b == nil {
            continue
        }
        if a == nil || b == nil {
            return false
        }
        if a.Val != b.Val {
            return false
        }
        Q = append(Q, []*TreeNode{a.Left, b.Left})
        Q = append(Q, []*TreeNode{a.Right, b.Right})
    }
    return true
}

We store a pair of nodes in the queue - and check them for equality. If they are equal - we continue push their corresponding children into the queue. If non-equality are found, we return false, otherwise, when the BFS exits, we return the true.

Same Binary Tree Check Algorithm:

Reposted to Blog