Solution


Approach 1: Recursion

Intuition

The simplest strategy here is to use recursion. Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.

Implementation

!?!../Documents/100_LIS.json:1000,373!?!

Complexity Analysis

  • Time complexity : , where N is a number of nodes in the tree, since one visits each node exactly once.

  • Space complexity : in the best case of completely balanced tree and in the worst case of completely unbalanced tree, to keep a recursion stack.


Approach 2: Iteration

Intuition

Start from the root and then at each iteration pop the current node out of the deque. Then do the same checks as in the approach 1 :

  • p and p are not None,

  • p.val is equal to q.val,

and if checks are OK, push the child nodes.

Implementation

Complexity Analysis

  • Time complexity : since each node is visited exactly once.

  • Space complexity : in the best case of completely balanced tree and in the worst case of completely unbalanced tree, to keep a deque.

Analysis written by @liaison and @andvary