Leetcode-Same Tree(Kotlin)

Overview

What You’ll Learn

This is an easy Leetcode problem. I am going to discuss my approach to solving the problem using the Kotlin programming language. The problem statement asks us to check if two binary trees are structurally identical and have the same values.

First I will show you the problem statement, examples and constraints given.

Also, check out this video tutorial on implementing these solutions:

In-order Traversal vs Breadth-first search

My first idea was to do an in-order traversal of both of the trees and check that way. The fact that it needs to be structurally identical made me think of also doing a breadth-first search. I ended up choosing the breadth-first search approach.

• First I created a queue and added both nodes to it. While the size is greater than 0, I get two nodes at a time and check the similarities here.

• Next, I check if either node is null. This handles the case that they are not structurally identical (Example 2 above).

• My last check is if both values at the level are the same.

• If all of those checks pass, I add both nodes’ children to the queue.

• Lastly, if all of the checks pass for every level, I will return true, since both trees are the same.

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    val queue = LinkedList<TreeNode?>()
    queue.offer(p)
    queue.offer(q)

    while(queue.size > 0){
        val one = queue.poll()
        val two = queue.poll()

        if(one == null && two == null) continue
        if(one == null || two == null) return false
        if(one.`val` != two.`val`) return false

        queue.offer(one?.left)
        queue.offer(two?.left)
        queue.offer(one?.right)
        queue.offer(two?.right)

    }

    return true
}

Congratulations

Congratulations, we have went through a couple of ways to solve Leetcode - Same Tree (Kotlin)!

Also, check out the video tutorial on implementing these solutions: