Solution


Approach 1: Annotate Parent and Depth

Intuition

Nodes are cousins if they have the same depth but different parents. A straightforward approach is to be able to know the parent and depth of each node.

Algorithm

We can use a depth-first search to annotate each node. For each node with parent par and depth d, we will record results in hashmaps: parent[node.val] = par and depth[node.val] = d.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the tree.

  • Space Complexity: .


Analysis written by: @awice.