Cousins in Binary Tree

This problem can be solved using a depth-first search (DFS) or breadth-first search (BFS) strategy. I will solve it using DFS. Here, I use two helper functions to get the depth and parent of the given nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        self._isCousins = False
        self.dx, self.px, self.dy, self.py = None, None, None, None

        if root is None:
            return False

        self.dfs(root, 0, None, x, y)
        return self._isCousins

    def dfs(self, node: TreeNode, depth: int, parent: TreeNode, x: int, y: int):
        if node is None:
            return

        if node.val == x or node.val == y:
            if self.dx is None:
                self.dx, self.px = depth, parent
            else:
                self.dy, self.py = depth, parent
                if self.dx == self.dy and self.px != self.py:
                    self._isCousins = True

        self.dfs(node.left, depth+1, node, x, y)
        self.dfs(node.right, depth+1, node, x, y)

In this code, dfs() is a helper function that performs a depth-first search through the binary tree. If it encounters a node with a value equal to x or y, it records the node’s depth and its parent. If it finds both x and y, it checks if they are at the same depth and have different parents. If they are, it sets self._isCousins to True. This value will then be returned by the isCousins() function.