deepSWE.io

Cousins in a Binary Tree

TreesBFS

Problem Statement

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.

Example

Input: root = [1,2,3,4], x = 4, y = 3

Output: false

Algorithm Explanation

We can solve this problem by finding the depth and parent of each of the two nodes, `x` and `y`.

Algorithm Steps

Find Depth and Parent: We can use a DFS or BFS traversal to find the depth and parent of both `x` and `y`.
Check Conditions: Once we have the depths and parents, we check if the depths are the same and the parents are different. If both conditions are met, the nodes are cousins.

Start

Starting DFS to find depths and parents.

xDepth: -1

xParent:

yDepth: -1

yParent:

Cousins in a Binary Tree Solution


class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        x_info = []
        y_info = []
        
        def dfs(node, parent, depth):
            if not node:
                return
            
            if node.val == x:
                x_info.extend([parent, depth])
            if node.val == y:
                y_info.extend([parent, depth])
            
            dfs(node.left, node, depth + 1)
            dfs(node.right, node, depth + 1)

        dfs(root, None, 0)
        return x_info[1] == y_info[1] and x_info[0] != y_info[0]