LeetCode 993 - Cousins in Binary Tree

The problem asks us to determine whether two nodes in a binary tree are cousins. Two nodes are considered cousins if they satisfy two conditions simultaneously: 1. They are located at the same depth in the tree. 2. They have different parents.

leetcodeeasytreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 993

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether two nodes in a binary tree are cousins. Two nodes are considered cousins if they satisfy two conditions simultaneously:

  1. They are located at the same depth in the tree.
  2. They have different parents.

The input consists of:

  • root, which is the root node of a binary tree.
  • Two integer values, x and y, representing the values of two distinct nodes in the tree.

Each node value in the tree is unique, which is important because it allows us to identify nodes solely by their values without ambiguity.

The expected output is a boolean:

  • Return true if the nodes corresponding to x and y are cousins.
  • Return false otherwise.

The tree depth starts at 0 for the root. Every child node is exactly one level deeper than its parent.

The constraints are relatively small:

  • The tree contains between 2 and 100 nodes.
  • Node values are unique and range from 1 to 100.

Because the tree is small, even less optimized solutions could pass comfortably. However, the goal is still to design a clean and efficient traversal strategy.

Several edge cases are important to recognize early:

  • If one node is the parent of the other, they cannot be cousins because their depths differ.
  • If both nodes share the same parent, they are siblings, not cousins.
  • If one node is the root, it cannot be a cousin of any other node because the root has no parent and depth 0.
  • The problem guarantees that both x and y exist in the tree, so we never need to handle missing targets.

Approaches

Brute Force Approach

A straightforward brute-force strategy is to independently search the tree twice:

  1. Find the depth of node x.
  2. Find the parent of node x.
  3. Find the depth of node y.
  4. Find the parent of node y.

After collecting this information, we compare:

  • Whether the depths are equal.
  • Whether the parents are different.

This approach works because the cousin definition depends only on these two properties.

One possible brute-force implementation repeatedly traverses the tree for each piece of information. For example:

  • One DFS to find depth of x
  • Another DFS to find parent of x
  • Another DFS to find depth of y
  • Another DFS to find parent of y

Although correct, this performs redundant work because the tree is traversed multiple times.

Optimal Approach

The key observation is that during a single traversal, we can collect both the depth and parent information for every target node.

A depth-first search naturally provides:

  • The current node depth.
  • The parent node reference.

As soon as we encounter x or y, we record:

  • Its depth.
  • Its parent.

Once both nodes are found, we simply compare:

  • Depth equality.
  • Parent inequality.

This reduces unnecessary repeated traversal and keeps the implementation clean and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) to O(4n) O(h) Multiple traversals of the tree to separately find depths and parents
Optimal O(n) O(h) Single DFS traversal collecting all required information

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

  1. Start a depth-first traversal from the root node.
  2. For every recursive call, keep track of:
  • The current node.
  • The parent node.
  • The current depth.
  1. When the current node's value equals x, record:
  • x_depth
  • x_parent
  1. When the current node's value equals y, record:
  • y_depth
  • y_parent
  1. Continue traversing both left and right subtrees until the entire tree has been explored or both targets have been found.
  2. After traversal completes, compare:
  • Whether x_depth == y_depth
  • Whether x_parent != y_parent
  1. Return True only if both conditions are satisfied.

Why it works

The algorithm works because every node in the tree is visited exactly once, and during traversal we accurately capture the two defining properties of cousin nodes:

  • Their depth in the tree.
  • Their parent node.

Two nodes are cousins if and only if they share the same depth while having different parents. Since DFS explores the entire tree and records this information correctly, the final comparison always produces the correct answer.

Python Solution

# 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: Optional[TreeNode], x: int, y: int) -> bool:
        x_info = None
        y_info = None

        def dfs(node, parent, depth):
            nonlocal x_info, y_info

            if not node:
                return

            if node.val == x:
                x_info = (parent, depth)

            if node.val == y:
                y_info = (parent, depth)

            dfs(node.left, node, depth + 1)
            dfs(node.right, node, depth + 1)

        dfs(root, None, 0)

        x_parent, x_depth = x_info
        y_parent, y_depth = y_info

        return x_depth == y_depth and x_parent != y_parent

The solution begins by initializing two variables, x_info and y_info, which will store the parent and depth information for the target nodes.

The nested dfs function performs recursive traversal. Each call receives:

  • The current node.
  • The parent node.
  • The current depth.

If the current node matches either x or y, the algorithm records its parent and depth as a tuple.

The recursion then continues into both left and right subtrees with depth incremented by one.

After traversal completes, both tuples contain the required information. The final return statement directly checks the cousin conditions:

  • Same depth.
  • Different parents.

Because the tree guarantees both nodes exist, unpacking the tuples is always safe.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
	var xParent, yParent *TreeNode
	var xDepth, yDepth int

	var dfs func(node *TreeNode, parent *TreeNode, depth int)

	dfs = func(node *TreeNode, parent *TreeNode, depth int) {
		if node == nil {
			return
		}

		if node.Val == x {
			xParent = parent
			xDepth = depth
		}

		if node.Val == y {
			yParent = parent
			yDepth = depth
		}

		dfs(node.Left, node, depth+1)
		dfs(node.Right, node, depth+1)
	}

	dfs(root, nil, 0)

	return xDepth == yDepth && xParent != yParent
}

The Go implementation follows the same logic as the Python version. The primary difference is that Go requires explicit variable declarations and uses pointers for tree nodes.

The recursive DFS function is declared using a function variable so that it can recursively reference itself.

Parent tracking is handled with *TreeNode pointers. Comparing parents becomes a simple pointer comparison:

xParent != yParent

The implementation also uses nil instead of Python's None.

Worked Examples

Example 1

Input:

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

Tree structure:

      1
     / \
    2   3
   /
  4

Traversal process:

Current Node Depth Parent Action
1 0 None Continue traversal
2 1 1 Continue traversal
4 2 2 Record x_info = (2, 2)
3 1 1 Record y_info = (1, 1)

Final values:

Node Parent Depth
4 2 2
3 1 1

Depths differ, so the nodes are not cousins.

Result:

false

Example 2

Input:

root = [1,2,3,null,4,null,5]
x = 5
y = 4

Tree structure:

      1
     / \
    2   3
     \   \
      4   5

Traversal process:

Current Node Depth Parent Action
1 0 None Continue traversal
2 1 1 Continue traversal
4 2 2 Record y_info = (2, 2)
3 1 1 Continue traversal
5 2 3 Record x_info = (3, 2)

Final values:

Node Parent Depth
5 3 2
4 2 2

The depths are equal and parents are different.

Result:

true

Example 3

Input:

root = [1,2,3,null,4]
x = 2
y = 3

Tree structure:

    1
   / \
  2   3
   \
    4

Traversal process:

Current Node Depth Parent Action
1 0 None Continue traversal
2 1 1 Record x_info = (1, 1)
4 2 2 Continue traversal
3 1 1 Record y_info = (1, 1)

Final values:

Node Parent Depth
2 1 1
3 1 1

The nodes share the same parent, so they are siblings, not cousins.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited at most once
Space O(h) Recursive call stack stores at most tree height frames

The DFS traversal touches each node exactly one time, resulting in linear time complexity relative to the number of nodes.

The space complexity depends on recursion depth. In a balanced tree, the height is approximately log n, while in a skewed tree it may become n.

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.left = TreeNode(4)

assert solution.isCousins(root1, 4, 3) == False  # different depths

# Example 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
root2.left.right = TreeNode(4)
root2.right.right = TreeNode(5)

assert solution.isCousins(root2, 5, 4) == True  # same depth, different parents

# Example 3
root3 = TreeNode(1)
root3.left = TreeNode(2)
root3.right = TreeNode(3)
root3.left.right = TreeNode(4)

assert solution.isCousins(root3, 2, 3) == False  # siblings

# Minimal valid tree
root4 = TreeNode(1)
root4.left = TreeNode(2)

assert solution.isCousins(root4, 1, 2) == False  # root cannot have cousins

# Deep skewed tree
root5 = TreeNode(1)
root5.left = TreeNode(2)
root5.left.left = TreeNode(3)
root5.left.left.left = TreeNode(4)

assert solution.isCousins(root5, 3, 4) == False  # parent-child relationship

# Cousins deeper in tree
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.right = TreeNode(3)
root6.left.left = TreeNode(4)
root6.right.right = TreeNode(5)

assert solution.isCousins(root6, 4, 5) == True  # classic cousin case

# Same depth but siblings
root7 = TreeNode(1)
root7.left = TreeNode(2)
root7.left.left = TreeNode(4)
root7.left.right = TreeNode(5)

assert solution.isCousins(root7, 4, 5) == False  # same parent
Test Why
[1,2,3,4], x=4, y=3 Verifies different depths are not cousins
[1,2,3,null,4,null,5], x=5, y=4 Standard cousin relationship
[1,2,3,null,4], x=2, y=3 Verifies siblings are not cousins
Minimal tree Checks smallest valid input
Deep skewed tree Tests recursion depth and parent-child distinction
Deep cousin case Validates cousin detection deeper in tree
Same depth siblings Ensures same parent is rejected

Edge Cases

One important edge case occurs when the two nodes are siblings. Since siblings naturally share the same depth, a naive solution that only checks depth equality would incorrectly return true. The implementation avoids this by explicitly recording and comparing parent nodes.

Another important edge case is a highly skewed tree, where every node has only one child. In such cases, recursion depth becomes equal to the number of nodes. The algorithm still works correctly because each recursive call properly tracks increasing depth and parent relationships.

A third important edge case involves the root node. The root has no parent and exists at depth 0, so it can never be a cousin with another node. The implementation handles this naturally because any other node must have depth greater than 0, causing the depth comparison to fail.

A final subtle case is when two nodes appear at the same depth but belong to completely different subtrees. This is actually the normal cousin scenario, and the DFS traversal correctly identifies it because parent tracking is independent for each subtree.