GoLang: Check Same Binary Trees via DFS or BFS Algorithms

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * 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)
}

/**
 * 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * 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) > 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
}

/**
 * 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) > 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:

• How to Check If Two Binary Trees are the Same?
• Teaching Kids Programming – Recursive Depth First Search Algorithm to Check If Two Binary Trees are Same
• GoLang: Check Same Binary Trees via DFS or BFS Algorithms
• Teaching Kids Programming – Breadth First Search Algorithm to Check If Two Binary Trees are Same

–EOF (The Ultimate Computing & Technology Blog) —