Cousins In Binary Tree - Leetcode Solution

Problem Statement:

Given a binary tree and two nodes of the tree p and q, the task is to find whether they are cousins or not.

Two nodes are said to be cousins of each other if they are at the same level of the binary tree and have different parents.

Solution:

To solve this problem, we will use a traversal algorithm (depth-first search, DFS). During the traversal, we will keep track of the following information for each node: its parent node, its level in the binary tree.

1. Traverse the binary tree using depth-first search.

2. For each node, record its level in the binary tree and its parent node.

3. If the levels of the given nodes (p and q) are the same and their parent nodes are different, then they are cousins.

4. If the levels of p and q are not the same, then they cannot be cousins.

Algorithm:

1. Initialize level and parent for root node.

2. Recursively traverse the binary tree and for each node:

   a. If the current node is a left child of the parent node, set the level and parent values for the left child node.

   b. If the current node is a right child of the parent node, set the level and parent values for the right child node.

3. Check if p and q have the same level and different parent nodes. If yes, return true, else return false.

Code:

class BinaryTreeNode:
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

def isCousin(root: BinaryTreeNode, p: BinaryTreeNode, q: BinaryTreeNode) -> bool:
    # level of p and q nodes
    pLevel = findLevel(root, p, 1)
    qLevel = findLevel(root, q, 1)
    # parent of p and q nodes
    pParent = findParent(root, p)
    qParent = findParent(root, q)
    # check if p and q are cousins
    return pLevel == qLevel and pParent != qParent

# find level of a node in binary tree
def findLevel(root: BinaryTreeNode, node: BinaryTreeNode, level: int) -> int:
    if root is None or node is None:
        return 0
    if root == node:
        return level
    # search the left subtree
    leftLevel = findLevel(root.left, node, level+1)
    if leftLevel != 0:
        return leftLevel
    # search the right subtree
    rightLevel = findLevel(root.right, node, level+1)
    return rightLevel

# find parent of a node in binary tree
def findParent(root: BinaryTreeNode, node: BinaryTreeNode) -> int:
    if root is None or node is None:
        return None
    if root.left == node or root.right == node:
        return root
    # search the left subtree
    leftParent = findParent(root.left, node)
    if leftParent is not None:
        return leftParent
    # search the right subtree
    rightParent = findParent(root.right, node)
    return rightParent
    

1