N3mo LC
Back to blog
Mar 03, 2024
19 min read

Cousins in Binary Tree

Check if two nodes in a binary tree are cousins (same depth, different parents).

Difficulty: Easy | Acceptance: 59.30% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Given the root of a binary tree with unique values and the values of two different nodes x and y, return true if the nodes corresponding to the values x and y are cousins. Otherwise, return false.

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

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

Examples

Example 1:

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

Explanation: The nodes with values 4 and 3 have different depths (4 is at depth 2, 3 is at depth 1).

Example 2:

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

Explanation: The nodes with values 5 and 4 have the same depth (both at depth 2) and different parents (5’s parent is 3, 4’s parent is 2).

Example 3:

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

Explanation: The nodes with values 2 and 3 have the same parent (1), so they are siblings, not cousins.

Constraints

The number of nodes in the tree is in the range [2, 100].
1 <= Node.val <= 100
Each node has a unique value.
x != y
x and y are present in the tree.

Approach 1: Depth-First Search (DFS)

Intuition Use DFS to find the depth and parent of both nodes x and y, then compare if they have the same depth but different parents.

Steps

  • Perform a DFS traversal of the tree.
  • For each node, track its depth and parent.
  • When we find node x, record its depth and parent.
  • When we find node y, record its depth and parent.
  • After traversal, check if depths are equal and parents are different.
python
# 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 = []
        y_info = []
        
        def dfs(node, depth, parent):
            if not node:
                return
            if node.val == x:
                x_info.append((depth, parent))
            if node.val == y:
                y_info.append((depth, parent))
            dfs(node.left, depth + 1, node.val)
            dfs(node.right, depth + 1, node.val)
        
        dfs(root, 0, None)
        return x_info[0][0] == y_info[0][0] and x_info[0][1] != y_info[0][1]

Complexity

  • Time: O(n) where n is the number of nodes in the tree
  • Space: O(h) where h is the height of the tree (recursion stack)
  • Notes: We traverse the entire tree in the worst case, and the space complexity depends on the tree height.

Approach 2: Breadth-First Search (BFS)

Intuition Use BFS to traverse the tree level by level, checking if x and y are at the same level with different parents.

Steps

  • Use a queue for BFS traversal.
  • For each level, check if x and y are present.
  • Track the parent of each node found.
  • If both x and y are found at the same level with different parents, return true.
  • If only one is found at a level, return false.
python
# 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
from collections import deque

class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        if not root:
            return False
        
        queue = deque([(root, None)])
        
        while queue:
            level_size = len(queue)
            x_found = False
            y_found = False
            x_parent = None
            y_parent = None
            
            for _ in range(level_size):
                node, parent = queue.popleft()
                
                if node.val == x:
                    x_found = True
                    x_parent = parent
                if node.val == y:
                    y_found = True
                    y_parent = parent
                
                if node.left:
                    queue.append((node.left, node.val))
                if node.right:
                    queue.append((node.right, node.val))
            
            if x_found and y_found:
                return x_parent != y_parent
            if x_found or y_found:
                return False
        
        return False

Complexity

  • Time: O(n) where n is the number of nodes in the tree
  • Space: O(w) where w is the maximum width of the tree (queue size)
  • Notes: BFS processes nodes level by level, which is natural for this problem since we need to check if nodes are at the same depth.

Approach 3: Single Pass DFS with Early Termination

Intuition Optimize the DFS approach by terminating early once both nodes are found, avoiding unnecessary traversal.

Steps

  • Perform DFS while tracking depth and parent.
  • Use instance variables to store information about x and y.
  • Stop recursion early if both nodes have been found.
  • Compare depth and parent after finding both nodes.
python
# 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:
        self.x_depth = -1
        self.y_depth = -1
        self.x_parent = None
        self.y_parent = None
        
        def dfs(node, depth, parent):
            if not node or (self.x_depth != -1 and self.y_depth != -1):
                return
            
            if node.val == x:
                self.x_depth = depth
                self.x_parent = parent
            if node.val == y:
                self.y_depth = depth
                self.y_parent = parent
            
            dfs(node.left, depth + 1, node.val)
            dfs(node.right, depth + 1, node.val)
        
        dfs(root, 0, None)
        return self.x_depth == self.y_depth and self.x_parent != self.y_parent

Complexity

  • Time: O(n) where n is the number of nodes in the tree (worst case)
  • Space: O(h) where h is the height of the tree (recursion stack)
  • Notes: Early termination can improve average case performance when nodes are found early in the traversal.

Approach 4: Iterative DFS

Intuition Use an explicit stack to simulate DFS traversal, avoiding recursion and tracking depth and parent for each node.

Steps

  • Use a stack to store (node, depth, parent) tuples.
  • Pop nodes from the stack and process them.
  • Track depth and parent for nodes x and y.
  • Compare depth and parent after finding both nodes.
python
# 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:
        if not root:
            return False
        
        stack = [(root, 0, None)]
        x_info = None
        y_info = None
        
        while stack:
            node, depth, parent = stack.pop()
            
            if node.val == x:
                x_info = (depth, parent)
            if node.val == y:
                y_info = (depth, parent)
            
            if x_info and y_info:
                break
            
            if node.right:
                stack.append((node.right, depth + 1, node.val))
            if node.left:
                stack.append((node.left, depth + 1, node.val))
        
        return x_info[0] == y_info[0] and x_info[1] != y_info[1]

Complexity

  • Time: O(n) where n is the number of nodes in the tree
  • Space: O(h) where h is the height of the tree (stack size)
  • Notes: Iterative DFS avoids recursion stack overflow issues for very deep trees and provides the same time complexity as recursive DFS.
Prev
Vowel-Consonant Score
Next
Rename Columns