Cousins in binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

59.1% acceptance

Feb 27, 2026

4311

233

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn is_cousins(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, x: i32, y: i32) -> bool {
    use std::collections::VecDeque;
    let mut queue: VecDeque<(Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, Option<i32>)> = VecDeque::new();
    queue.push_back((root, None));
    let mut _depth = 0;
    while !queue.is_empty() {
      let len = queue.len();
      let (mut x_parent, mut y_parent) = (None::<i32>, None::<i32>);
      for _ in 0..len {
        let (node, parent) = queue.pop_front().unwrap();
        if let Some(n) = node {
          let n = n.borrow();
          if n.val == x { x_parent = parent; }
          if n.val == y { y_parent = parent; }
          if let Some(l) = n.left.clone() { queue.push_back((Some(l), Some(n.val))); }
          if let Some(r) = n.right.clone() { queue.push_back((Some(r), Some(n.val))); }
        }
      }
      if x_parent.is_some() && y_parent.is_some() { return x_parent != y_parent; }
      if x_parent.is_some() || y_parent.is_some() { return false; }
      _depth += 1;
    }
    false
  }
}