Leetcode Question #100 (Same Tree)

Python Iterative BFS Level Order Search explained || Time O(n) || Space O(n)

From LeetCode: 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.

Intuition

• Simply do what you'd do if you were to do this visually, by looking at both the trees.

• If I were to do this by looking at it, I'd simply go left to right on each levels and check if the nodes match, which is basically the level order traversal of the tree.

• If the trees are the same, the nodes should match as I travers through them on both the trees.

Approach

1. define a queue and add a tuple containing both the root nodes to it

2. while tree is non-empty, get the pNode and qNode from the tuple and process them:

   1. are both nodes null? they are equal, continue on to the next tuple in the queue

   2. is just one of them null? return False and end the function since this would mean that the trees are not the same as nodes don't match

   3. are the values equal? if not, return False and end the function since this too would mean that the trees are not the same as nodes don't match

   4. create tuple pairs from left and right nodes of p and q and add them to the queue (don't worry about checking for null since we are doing that in #1 and #2 above when we process them).

Code

Complexity

• Time complexity: O(n), worst case the tree are same and we end up traversing all the nodes in which case n denotes the number of nodes in both tree (should be the same)

• Space complexity: O(n), in the worst case we will have _less than n_ nodes in the queue

---