Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Build confidence with an intuition-first walkthrough focused on tree fundamentals.
Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.
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 the depth 0, and children of each depth k node are at the depth k + 1.
Example 1:
Input: root = [1,2,3,4], x = 4, y = 3 Output: false
Example 2:
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true
Example 3:
Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false
Constraints:
[2, 100].1 <= Node.val <= 100x != yx and y are exist in the tree.Problem summary: Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise. 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 the depth 0, and children of each depth k node are at the depth k + 1.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
[1,2,3,4] 4 3
[1,2,3,null,4,null,5] 5 4
[1,2,3,null,4] 2 3
binary-tree-level-order-traversal)cousins-in-binary-tree-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #993: Cousins in Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
Deque<TreeNode[]> q = new ArrayDeque<>();
q.offer(new TreeNode[] {root, null});
int d1 = 0, d2 = 0;
TreeNode p1 = null, p2 = null;
for (int depth = 0; !q.isEmpty(); ++depth) {
for (int n = q.size(); n > 0; --n) {
TreeNode[] t = q.poll();
TreeNode node = t[0], parent = t[1];
if (node.val == x) {
d1 = depth;
p1 = parent;
} else if (node.val == y) {
d2 = depth;
p2 = parent;
}
if (node.left != null) {
q.offer(new TreeNode[] {node.left, node});
}
if (node.right != null) {
q.offer(new TreeNode[] {node.right, node});
}
}
}
return p1 != p2 && d1 == d2;
}
}
// Accepted solution for LeetCode #993: Cousins in Binary Tree
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isCousins(root *TreeNode, x int, y int) bool {
type pair struct{ node, parent *TreeNode }
var d1, d2 int
var p1, p2 *TreeNode
q := []pair{{root, nil}}
for depth := 0; len(q) > 0; depth++ {
for n := len(q); n > 0; n-- {
node, parent := q[0].node, q[0].parent
q = q[1:]
if node.Val == x {
d1, p1 = depth, parent
} else if node.Val == y {
d2, p2 = depth, parent
}
if node.Left != nil {
q = append(q, pair{node.Left, node})
}
if node.Right != nil {
q = append(q, pair{node.Right, node})
}
}
}
return d1 == d2 && p1 != p2
}
# Accepted solution for LeetCode #993: Cousins in Binary Tree
# 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
// Accepted solution for LeetCode #993: Cousins in Binary Tree
struct Solution;
use rustgym_util::*;
trait Preorder {
fn preorder(&self, depth: usize, parent: i32, res: &mut Option<(usize, i32)>, v: i32);
}
impl Preorder for TreeLink {
fn preorder(&self, depth: usize, parent: i32, res: &mut Option<(usize, i32)>, v: i32) {
if res.is_some() {
return;
}
if let Some(node) = self {
let node = node.borrow();
let val = node.val;
if v == val {
*res = Some((depth, parent));
}
node.left.preorder(depth + 1, val, res, v);
node.right.preorder(depth + 1, val, res, v);
}
}
}
impl Solution {
fn is_cousins(root: TreeLink, x: i32, y: i32) -> bool {
let mut rx: Option<(usize, i32)> = None;
let mut ry: Option<(usize, i32)> = None;
root.preorder(0, 0, &mut rx, x);
root.preorder(0, 0, &mut ry, y);
if let (Some((dx, px)), Some((dy, py))) = (rx, ry) {
dx == dy && px != py
} else {
false
}
}
}
#[test]
fn test() {
let root = tree!(1, tree!(2, tree!(4), None), tree!(3));
let x = 4;
let y = 3;
let res = false;
assert_eq!(Solution::is_cousins(root, x, y), res);
let root = tree!(1, tree!(2, None, tree!(4)), tree!(3, None, tree!(5)));
let x = 5;
let y = 4;
let res = true;
assert_eq!(Solution::is_cousins(root, x, y), res);
let root = tree!(1, tree!(2, None, tree!(4)), tree!(3));
let x = 2;
let y = 3;
let res = false;
assert_eq!(Solution::is_cousins(root, x, y), res);
}
// Accepted solution for LeetCode #993: Cousins in Binary Tree
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
let [d1, d2] = [0, 0];
let [p1, p2] = [null, null];
const q: [TreeNode, TreeNode][] = [[root, null]];
for (let depth = 0; q.length > 0; ++depth) {
const t: [TreeNode, TreeNode][] = [];
for (const [node, parent] of q) {
if (node.val === x) {
[d1, p1] = [depth, parent];
} else if (node.val === y) {
[d2, p2] = [depth, parent];
}
if (node.left) {
t.push([node.left, node]);
}
if (node.right) {
t.push([node.right, node]);
}
}
q.splice(0, q.length, ...t);
}
return d1 === d2 && p1 !== p2;
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.