What is the brute force approach and complexity for Cousins in Binary Tree?

Search for x and record its depth and parent; do the same for y; then compare the two records with time complexity O(N) and space complexity O(H).

Cousins in Binary Tree

Q: How do you identify the pattern for Cousins in Binary Tree?

Look for key signals in the prompt: "same depth" indicates Both nodes must be in the same BFS round, so the round is the unit to check.; "different parents" indicates No single node may hold both as children. BFS can check this when it pops a node, because its children are right there.; "x and y both exist" indicates If a round finds only one of them, the other one is somewhere else, so the answer is false..

Easy·LeetCode #993 Pro OnlyMedium

LeetCode

Problem Statement

You are given the root of a binary tree, where every value is different, and two values x and y. Both values are in the tree, and they are not equal.

Return true if the nodes holding x and y are cousins, otherwise return false.

Two nodes are cousins when they are on the same depth and have different parents. The root is at depth 0, and the children of a node at depth k are at depth k + 1.

Input

The root of a binary tree, and two different values x and y. Every value in the tree is unique, and both x and y exist in it.

Output

true if the two nodes are cousins, otherwise false.

Example 1

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

Output: false

4 is at depth 2 and 3 is at depth 1. They are on different depths.

Example 2

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

Output: true

4 is at depth 2 under 2, and 5 is at depth 2 under 3. Same depth, different parents.

Example 3

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

Output: false

2 and 3 are both children of the root. Same depth, but the same parent, so they are siblings and not cousins.

Constraints

• The number of nodes is between 2 and 100.
• 1 ≤ Node.val ≤ 100
• Every node has a unique value.
• x ≠ y
• x and y both exist in the tree.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“same depth”

→ Both nodes must be in the same BFS round, so the round is the unit to check.

“different parents”

→ No single node may hold both as children. BFS can check this when it pops a node, because its children are right there.

“x and y both exist”

→ If a round finds only one of them, the other one is somewhere else, so the answer is false.

Approach Complexity Ladder

Brute Force — two separate searches for depth and parentO(N)O(H)

Search for x and record its depth and parent; do the same for y; then compare the two records

Optimal — BFS, check siblings and both values in one roundO(N)O(W)

Walk one depth at a time; in each round check each node's children for a sibling pair, then check whether both values were seen

Brute Force Intuition

Run one depth-first search for x that records its depth and its parent. Run a second search for y the same way. The answer is true when the two depths are equal and the two parents are different.

Recognition rule for this sub-pattern:

Compute something per level: last node (right view), max, average, width.

Remember this · Tree BFS

Trigger

Level order, per-level max/average, right side view, minimum depth, nodes at distance k.

Think

Does the question care about depth / rows rather than paths?

Key question

How many nodes are in the current level (queue size at the start of the level)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture