Leetcode – Cousins in Binary Tree Solution in Python

Spread the love

Binary trees are a fundamental data structure in computer science, serving as the backbone for many algorithms and applications. One interesting problem related to binary trees is the “Cousins in Binary Tree” challenge available on Leetcode. This problem tests one’s ability to traverse and interpret relationships within a binary tree. This article provides a comprehensive look into this problem, discussing the problem statement, breaking down the solution strategy, and offering Python implementations.

Table of Contents

  1. Problem Statement
  2. Understanding the Problem
  3. Depth-First Search (DFS) Solution
  4. Breadth-First Search (BFS) Solution
  5. Time and Space Complexity Analysis
  6. Conclusion

1. Problem Statement

Given the root of a binary tree and two integers x and y, return true if the values represented by x and y are cousins, otherwise return false.Two nodes are considered cousins if:

  • They are on the same level in the tree.
  • They have different parent nodes.

Example:

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

2. Understanding the Problem

Before diving into the solution, we need to clarify what it means for two nodes to be “cousins”. Nodes are cousins if:

  1. They are at the same depth or level in the tree.
  2. They don’t share the same parent.

Given these criteria, our task is to traverse the binary tree and check these two conditions for the nodes x and y.

3. Depth-First Search (DFS) Solution

Using DFS, we can traverse the tree and, during the traversal, record the depth and parent for each node. Once we have the depth and parent for both x and y, we can determine if they’re cousins.

Python Implementation:

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

def isCousins(root, x, y):
    # This helper function updates the depth and parent information
    def dfs(node, parent, depth):
        if not node:
            return
        if node.val == x or node.val == y:
            depths[node.val] = depth
            parents[node.val] = parent
        dfs(node.left, node, depth + 1)
        dfs(node.right, node, depth + 1)

    depths = {}
    parents = {}
    dfs(root, None, 0)
    
    # Check the two conditions for being cousins
    return depths[x] == depths[y] and parents[x] != parents[y]

4. Breadth-First Search (BFS) Solution

An alternative approach uses BFS. We can traverse the tree level by level and check if x and y are on the same level but have different parents.

Python Implementation:

from collections import deque

def isCousins(root, x, y):
    queue = deque([(root, None)])  # Each item is a pair (node, parent)

    while queue:
        level_length = len(queue)
        found_x, found_y = None, None  # Store the parents of nodes x and y if they're found at the current level

        for i in range(level_length):
            node, parent = queue.popleft()
            if node.val == x:
                found_x = parent
            if node.val == y:
                found_y = parent

            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))
        
        # If only one of x or y is found on this level, they can't be cousins
        if (found_x and not found_y) or (found_y and not found_x):
            return False
        # If x and y are found and they have different parents, they are cousins
        if found_x and found_y and found_x != found_y:
            return True

    return False

5. Time and Space Complexity Analysis

  • DFS Solution:
    • Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once.
    • Space Complexity: O(n) in the worst case, due to the recursive call stack. In a balanced tree, it would be O(log⁡n).
  • BFS Solution:
    • Time Complexity: O(n) as we might need to traverse all nodes.
    • Space Complexity: O(n) for the queue in the worst case, when the last level of the tree is fully populated.

6. Conclusion

The “Cousins in Binary Tree” problem on Leetcode is a fascinating challenge that not only tests one’s ability to traverse a binary tree but also one’s understanding of tree structures and relationships within them. Whether using DFS or BFS, the core of the solution revolves around identifying node relationships and depth in the tree. Practicing problems like these can greatly enhance one’s proficiency with tree-based algorithms and data structures.

Leave a Reply