100.same-tree.md

100. Same Tree

Test Cases

Normal Cases

Input: 
    1
  /   \
 2     3

    1
  /   \
 2     3
Output: True

Edge / Corner Cases

• Values are the same, but different structurely.

Input: 
    1
  /   
 2  

// Or
    1
      \
       2
Output = False

• Same structurely, but different value.

Input: 
    1
  /   
 2  
    1
  /   
 3
Output = False

Recursive

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    if (p == null && q == null) return true
    if (p == null || q == null) return false
    return (p.`val` == q.`val`) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

• Time Complexity: O(min(P, Q)), where P and Q are the number of tree nodes of p and q, we terminate the recursion when we reach the end of the smaller tree.
• Space Complexity: O(min(Hp, Hq)), where Hp and Hq are the height of the tree of p and q.

Iterative

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    val pQueue = ArrayDeque<TreeNode?>()
    val qQueue = ArrayDeque<TreeNode?>()
    pQueue.addLast(p)
    qQueue.addLast(q)
    while (pQueue.isNotEmpty() && qQueue.isNotEmpty()) {
        val pp = pQueue.removeFirst()
        val qq = qQueue.removeFirst()

        if (pp == null && qq == null) continue
        if (pp == null || qq == null) return false
        if (pp.`val` != qq.`val`) return false
        pQueue.addLast(pp.left)
        pQueue.addLast(pp.right)
        
        qQueue.addLast(qq.left)
        qQueue.addLast(qq.right)
    }
    return pQueue.isEmpty() && qQueue.isEmpty()
}

• Time Complexity: O(min(P, Q)), where P and Q are the number of tree nodes of p and q.
  • We process nodes level by level until we find a mismatch or reach the end of the smaller tree
  • Each node is visited at most once
• Space Complexity: O(min(P, Q))
  • The queue can hold at most all nodes from the smaller tree
  • In worst case, when trees are complete binary trees, the last level can have O(min(P, Q)) nodes

Traversal

private val pNodes = mutableListOf<Int?>()
private val qNodes = mutableListOf<Int?>()

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    inOrderTraversal(p, pNodes)
    inOrderTraversal(q, qNodes)

    if (pNodes.size != qNodes.size) return false
    else {
        for (i in 0 until pNodes.size) {
            if (pNodes[i] != qNodes[i]) return false
        }
    }
    return true
}

private fun inOrderTraversal(node: TreeNode?, results: MutableList<Int?>) {
    results.add(node?.`val`)
    // We can't skip the null node, we have to add null value for it.
    if (node?.left != null) inOrderTraversal(node?.left, results) else results.add(null)
    if (node?.right != null) inOrderTraversal(node?.right, results) else results.add(null)
}

• Time Complexity: O(max(P, Q)), where |P| and |Q| are the number of tree nodes of p and q.
• Space Complexity: O(P + Q)