Leetcode - Same Tree (Kotlin)

#leetcode #kotlin #android #interview

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

They give us three examples shown below:

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.
The first check I make is if both of the nodes are null. In this case, we are probably after two leaf nodes from both trees.

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
 }