#993

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Cousins in Binary Tree

Determine if two nodes in a binary tree are cousins by leveraging binary-tree traversal and state tracking.

tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree with unique values, and two distinct nodes with values x and y, determine if they are cousins. Nodes are considered cousins if they are on the same level but have different parents. The root node is at depth 0, and each child is at a depth of 1 greater than its parent.

To solve this problem, traverse the binary tree using Depth-First Search (DFS) or Breadth-First Search (BFS), and track the depth and parent of each node. Compare the depths of x and y to check if they are the same, and ensure their parents differ. If both conditions hold, they are cousins.

Examples

Example 1

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

Output: false

Example details omitted.

Example 2

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

Output: true

Example details omitted.

Example 3

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

Output: false

Example details omitted.

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 exist in the tree.

Solution Approach

Depth-First Search (DFS)

DFS can be used to traverse the tree recursively. During the traversal, record the depth and parent of each node. Once both x and y are found, compare their depths and ensure their parents are different.

Breadth-First Search (BFS)

BFS is another viable approach, where nodes are explored level by level. During BFS, track the parent and depth of each node, ensuring to stop when both x and y are found at the same level with distinct parents.

State Tracking

Whether using DFS or BFS, effective state tracking of parent-child relationships and depths is crucial. Once both nodes are located, it’s important to compare their levels and parents to conclude if they are cousins.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the traversal method. Both DFS and BFS have a time complexity of O(n), where n is the number of nodes in the tree, since each node is visited once. The space complexity is also O(n), as additional space is required to store the nodes in the call stack (DFS) or the queue (BFS).

What Interviewers Usually Probe

The candidate understands tree traversal techniques such as DFS and BFS.
The candidate effectively explains the importance of tracking the parent and depth of nodes.
The candidate can recognize the distinction between cousins and other types of nodes in a tree.

Common Pitfalls or Variants

Common pitfalls

Confusing cousins with sibling nodes. Cousins are at the same depth but have different parents, unlike siblings who share the same parent.
Not handling edge cases where x or y might be near the root or leaf nodes.
Incorrectly assuming that BFS or DFS will automatically find cousins without tracking depth and parent.

Follow-up variants

The problem could be modified to find multiple cousin pairs in a single tree traversal.
The tree could be unbalanced, potentially affecting traversal strategy and performance.
The problem could ask for the path from the root to a given node, requiring depth and parent tracking.

FAQ

What is the main concept tested in the Cousins in Binary Tree problem?

The problem tests binary-tree traversal and state tracking, specifically identifying cousin nodes by comparing their depth and parent.

Can this problem be solved using BFS?

Yes, BFS can be used to traverse the tree level by level, tracking parent and depth to check if the nodes are cousins.

What are the common mistakes when solving the Cousins in Binary Tree problem?

A common mistake is confusing cousins with siblings or not properly tracking the parent and depth during traversal.

What is the time complexity of solving the Cousins in Binary Tree problem?

The time complexity is O(n), where n is the number of nodes in the tree, as each node needs to be visited once.

How can GhostInterview help with this problem?

GhostInterview helps by guiding you through traversal techniques like DFS and BFS, ensuring you avoid pitfalls like mixing up cousins and siblings, and preparing you to explain your approach clearly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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:
        q = deque([(root, None)])
        depth = 0
        p1 = p2 = None
        d1 = d2 = None
        while q:
            for _ in range(len(q)):
                node, parent = q.popleft()
                if node.val == x:
                    p1, d1 = parent, depth
                elif node.val == y:
                    p2, d2 = parent, depth
                if node.left:
                    q.append((node.left, node))
                if node.right:
                    q.append((node.right, node))
            depth += 1
        return p1 != p2 and d1 == d2

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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:
        q = deque([(root, None)])
        depth = 0
        p1 = p2 = None
        d1 = d2 = None
        while q:
            for _ in range(len(q)):
                node, parent = q.popleft()
                if node.val == x:
                    p1, d1 = parent, depth
                elif node.val == y:
                    p2, d2 = parent, depth
                if node.left:
                    q.append((node.left, node))
                if node.right:
                    q.append((node.right, node))
            depth += 1
        return p1 != p2 and d1 == d2

Continue Practicing

#987 vertical order traversal of a binary tree #965 univalued binary tree #865 smallest subtree with all the deepest nodes