Show problems as
Classic problem #993EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Cousins in Binary Tree

Real-world version: Do Two Lamps Hang as Cousins
Tracked in this browser only
Read Cousins in Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A frame hangs from a single top lamp. Every lamp holds at most two lamps below it in a first and a second slot, and either slot may be empty. Every lamp carries a different label.

A flat list is read level by level: its first entry is the top lamp's label, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own.

Two lamps are cousins when they hang the same number of slots below the top lamp and they do not hang from the same lamp.

The labels x and y are different and both appear in the frame. Return true when the lamps carrying them are cousins.

Examples

Example 1

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

Both lamps hang two slots below the top. Lamp 4 hangs from lamp 2 and lamp 5 hangs from lamp 3, so they are cousins.

Example 2

Input
frame = [1, 2, 3], x = 2, y = 3
Output
false

The two lamps hang the same distance down, but both of them hang from the top lamp.

Example 3

Input
frame = [1, 2, 3, 4, 5, 6, 7], x = 4, y = 3
Output
false

Lamp 4 hangs two slots down while lamp 3 hangs only one, so the distances differ.

Constraints

  • 2 <= frame.length <= 200
  • The frame holds between 2 and 100 lamps.
  • 1 <= frame[i] <= 100
  • no two lamps carry the same label
  • x != y
  • both x and y appear in the frame

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def is_cousins(frame: list, x: int, y: int) -> bool:
Java
public boolean isCousins(Integer[] frame, int x, int y)

More on the same topics