LeetCode 993: Cousins in Binary Tree – DFS and BFS Approaches Explained (Python)

LeetCode 993: Cousins in Binary Tree – DFS and BFS Explained (Python)

In this post, I’ll walk through my two solutions to LeetCode Problem 993: Cousins in Binary Tree, using both a recursive DFS approach and an *iterative BFS * approach. Each method has its own strengths, and I explain how I used them to solve the problem cleanly in Python.

🧠 Problem Overview

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

Given the root of a binary tree with unique values, and the values of two different nodes x and y, return True if they are cousins, False otherwise.

Overall approach

It is guaranteed that nodes with the value x and y exists, so in each of the 2 solutions we should make sure that those nodes’ parents and depths are tracked and compared correctly

First approach DFS: Depth First Search

We define helper function called findNodeDepth which recursively searches for the node first in left subtree, if not found, function searches it in right subtree. When the node is found its depth and parent is returned

Here is the full code:

def isCousins(self, root, x, y):
    depth1, parent1 = self.findNodeDepth(root, x, 0, None)
    depth2, parent2 = self.findNodeDepth(root, y, 0, None)

    if (depth1 == depth2 and parent1 != parent2): 
        return True
    return False

def findNodeDepth(self, root, x, depth, prev):
    if root == None: 
        return None
    if root.val == x: 
        return (depth, prev)

    left = self.findNodeDepth(root.left, x, depth + 1, root)
    if left: return left

    return self.findNodeDepth(root.right, x, depth + 1, root)

Enter fullscreen mode Exit fullscreen mode

At the end it compares their depth and parent according to the problem statement such that it will return True if their depth are equal and parents are different, False otherwise.

Second Approach: Breadth-First Search

Overall logic is similar but this time we traverse the tree such that nodes in the same depth are visited first, which makes sense to do if we are looking for cousins.

Here’s the full code:

from collections import deque

def isCousins(self, root, x, y):
    queue = deque()
    queue.append((root, None, 0))  # (node, parent, depth) 
    node1, node2 = None, None

    while queue:
        size = len(queue)
        for _ in range(size):
            node, parent, depth = queue.popleft()

            if node.val == x:
                node1 = (node, parent, depth)
            elif node.val == y:
                node2 = (node, parent, depth)

            if node.left:
                queue.append((node.left, node, depth + 1))
            if node.right:
                queue.append((node.right, node, depth + 1))

        if node1 and node2:
            return node1[1] != node2[1] and node1[2] == node2[2]
        elif node1 or node2:
            return False

    return False

Enter fullscreen mode Exit fullscreen mode

Perfect for checking whether two nodes are at the same level, and have different parents.

Final Thoughts

Writing out both helped me understand how traversal methods affect problem-solving in trees — and I recommend trying both when you study similar problems.

Let’s Connect

If you liked this breakdown, feel free to follow me.
I’ll be sharing more clean solutions and dev thoughts regularly.

原文链接：LeetCode 993: Cousins in Binary Tree – DFS and BFS Approaches Explained (Python)