Max Rukomoynikov

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.

This implementation of isSameTree takes a level-order (breadth-first) approach using two queues to compare the trees level by level. Each queue maintains the nodes for one tree, and the algorithm processes nodes in parallel from both trees. The outer while loop continues as long as both queues have nodes to process, while the inner for loop handles each level of the trees by processing the current level's worth of nodes (tracked by node1LevelLength). For each pair of nodes dequeued, it performs the familiar three-way comparison: both null nodes are skipped, mismatched null states indicate different structures, and different values indicate non-identical trees. After each successful node comparison, the left and right children of both nodes are enqueued for later processing. This level-by-level traversal ensures that nodes at the same positions in both trees are compared in a predictable order, moving from top to bottom and left to right. The approach has the same O(n) time complexity as the other versions but provides a different traversal pattern that might be more suitable for certain applications, particularly when level-order processing is desired.

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  let node1Queue = [p]
  let node2Queue = [q]

  while(node1Queue.length && node2Queue.length) {
    let node1LevelLength = node1Queue.length
    let node2LevelLength = node2Queue.length

    for(let i = 0; i < node1LevelLength; i++) {
      let node = node1Queue.shift()
      let node2 = node2Queue.shift()

      if(node == null && node2 == null) continue
      if(node == null || node2 == null) return false
      if(node.val != node2.val) return false


      node1Queue.push(node.left)
      node1Queue.push(node.right)

      node2Queue.push(node2.left)
      node2Queue.push(node2.right)
    }

  }

  return true
}

It uses an iterative approach with a stack instead of recursion. It maintains a stack of node pairs to be compared, initially containing the root nodes of both trees. In each iteration, it pops a pair of nodes from the stack and performs the same three key comparisons as the recursive version: if both nodes are null, it continues to the next pair; if exactly one node is null, the trees differ in structure (returns false); and if the values don't match, the trees are different (returns false). The key difference is that instead of making recursive calls, it explicitly pushes the left and right child pairs onto the stack for future comparison. The stack manages the traversal order, effectively mimicking the call stack that would be created in the recursive version. The function returns true only if all node pairs have been processed without finding any mismatches, meaning the trees are identical. This iterative approach can be more space-efficient than recursion for very deep trees, as it won't create a deep call stack.

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  let stack = [[p, q]]

  while(stack.length) {
    let [node1, node2] = stack.pop()

    if(node1 == null && node2 == null) continue
    if(node1 == null || node2 == null) return false
    if(node1.val != node2.val) return false

    stack.push([node1.left, node2.left])
    stack.push([node1.right, node2.right])
  }

  return true
};

It uses a recursive approach that checks three base cases: first, if both nodes are null, the trees are identical at this point (returns true); second, if exactly one node is null while the other isn't, the trees have different structures (returns false); and third, if the current nodes' values don't match, the trees are different (returns false). If all these checks pass, the function recursively compares the left and right subtrees of both nodes, using the AND operator (&&) to ensure both subtrees match. This depth-first traversal continues until either a mismatch is found or all nodes have been verified to match, effectively comparing the entire structure and values of both trees in O(n) time, where n is the number of nodes in the tree.

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if(p == null && q == null) return true
  if(p == null || q == null) return false
  if(p.val != q.val) return false

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}