993. Cousins In A Binary Tree 1

Problem Statement in English

You’re given the root of a binary tree with unique values, and the values of two different nodes of the tree x and y.

Return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Approach

We can use a hashmap to store the depth and parent of each node. We can do a DFS traversal of the tree and fill the hashmap.

After that, we can check if the depth of x and y are the same and if their parents are different.

And we’re done!

Solution in Python

class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        hm = {}

        def dfs(node, parent, depth):
            hm[node.val] = (depth, parent)

            if node.left:
                dfs(node.left, node, depth + 1)
            
            if node.right:
                dfs(node.right, node, depth + 1)

        dfs(root, None, 0)

        d1, p1 = hm[x]
        d2, p2 = hm[y]

        if d1 == d2 and p1 != p2:
            return True
        return False
            

Complexity

• Time: $O(n)$
  Since we traverse the tree once.

• Space: $O(n)$
  Since we store the depth and parent of each node in a hashmap.

And we are done.