Same Tree

Problem

• 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.

Approach

• 1. Base cases: if both nodes are null (leaves), return true safely. If one node is null and the other isn't there's an imbalance. If the node values aren't equal, they're not the same.
• 2. After passing all of the base cases, check if the tree's left and right subtree are true/false recursively, ensure both left and right are true at the end.

Reflections

Fairly simple DFS problem in all honesty. One issue I did recognize fairly quickly was that I was using one truthy value for the left and right side, so if right was true it would return true, even when left was false.

Go Solution

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
  }

  left:= isSameTree(p.Left, q.Left)
  right:= isSameTree(p.Right, q.Right)

  return left && right
}

Performance

• Runtime beats: 100%
• Memory beats: 99.4%

Complexity

• Time: O(n)
• Space: O(n)