---
tags: data_structure_python
---

# Cousins in Binary Tree <img src="https://img.shields.io/badge/-easy-brightgreen">

In a binary tree, the root node is at depth `0`, and children of each depth `k` node are at depth `k+1`.

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

We are given the `root` of a binary tree with unique values, and the values `x` and `y` of two different nodes in the tree.

Return `true` if and only if the nodes corresponding to the values `x` and `y` are cousins.

**Example 1:**


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

**Example 2:**


Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

**Example 3:**


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

**Note:**

- The number of nodes in the tree will be between `2` and `100`.
- Each node has a unique integer value from `1` to `100`.

- [] Check BFS optmize
- [] Check DFS

# Solution

## Solution 1.1: BFS using level marker + variables (attempt 1)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = [root, None]
        depthX, depthY = 0, 0
        parentX, parentY = None, None
        h = 0
        
        while len(queue) > 0:
            node = queue.pop(0)
        
            if node == None:
                if len(queue) > 0: # Level marker.
                    h += 1
                    queue.append(None)
            else:
                if node.val == x:
                    depthX = h
                if node.val == y:
                    depthY = h
                    
                if node.left != None:
                    queue.append(node.left)
                    
                    if node.left.val == x:
                        parentX = node
                    if node.left.val == y:
                        parentY = node
                       
                if node.right != None:
                    queue.append(node.right)    
                    
                    if node.right.val == x:
                        parentX = node
                    if node.right.val == y:
                        parentY = node
        
      if depthX == depthY and parentX != parentY:
            return True
        
        return False

## Solution 1.2: BFS using depth/parent tuple (attempt 2)

- In this solution, we have to traverse the entire tree before returning False/True.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = [(root, 0, None)]
        treeDict = {}
        
        while len(queue) > 0:
            node, depth, parent = queue.pop(0)
            if node != None:
                treeDict[node.val] = depth, parent
                queue.append((node.left, depth+1, node.val))
                queue.append((node.right, depth+1, node.val))    

        return treeDict[x][0] == treeDict[y][0] and treeDict[x][1] != treeDict[y][1]

## Solution 1.3: BFS using depth/parent tuple + deque (attempt 3)

- We should use a deque instead of a simple list because a deque's popleft() (remove the first element) has O(1) instead of O(n) for a list's pop(0).

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = deque()
        queue.append((root, 0, None))
        treeDict = {}
        
        while len(queue) > 0:
            node, depth, parent = queue.popleft()
            if node != None:
                treeDict[node.val] = depth, parent
                queue.append((node.left, depth+1, node.val))
                queue.append((node.right, depth+1, node.val))    

        return treeDict[x][0] == treeDict[y][0] and treeDict[x][1] != treeDict[y][1]

## Solution 1.4: BFS using depth/parent tuple + deque + variable (attempt 4)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        queue = deque()
        queue.append((root, 0, None))
        parentX, parentY = None, None
        depthX, depthY = 0, 0
        
        while len(queue) > 0:
            node, depth, parent = queue.popleft()
                        
            if node != None:
                
                if node.val == x:
                    parentX, depthX = parent, depth
                if node.val == y:
                    parentY, depthY = parent, depth
                
                queue.append((node.left, depth+1, node.val))
                queue.append((node.right, depth+1, node.val))    

        return depthX == depthY and parentX != parentY
       

## Solution 1.5: DFS

# Definition for a binary tree node.
 class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

class Solution:
    def dfs(self, node, parent, depth, x, y, treeDict):
        if node == None:
            return
        if node.val == x or node.val == y:
            treeDict.append((parent, depth))
        
        self.dfs(node.left, node, depth+1, x, y, treeDict)
        self.dfs(node.right, node, depth+1, x, y, treeDict)
        
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:       
        treeDict = []
        self.dfs(root, None, 0, x, y, treeDict)
        return treeDict[0][1] == treeDict[1][1] and treeDict[0][0] != treeDict[1][0]