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