Validate binary tree nodes

Tree Depth-First Search Breadth-First Search Union-Find Graph Theory Binary Tree

44.1% acceptance

Feb 25, 2026

2249

524

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree. If node i has no left child then leftChild[i] will equal -1, similarly for the right child. Note that the nodes have no values and that we only use the node numbers in this problem.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
    let n = n as usize;
    let mut parent = vec![-1i32; n];
    // Build parent relationship
    for i in 0..n {
      for &child in &[left_child[i], right_child[i]] {
        if child == -1 { continue; }
        let c = child as usize;
        if parent[c] != -1 { return false; } // multiple parents
        parent[c] = i as i32;
      }
    }
    // Find root: node with no parent
    let roots: Vec<usize> = (0..n).filter(|&i| parent[i] == -1).collect();
    if roots.len() != 1 { return false; }
    // BFS to check connectivity
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(roots[0]);
    visited[roots[0]] = true;
    let mut count = 1;
    while let Some(node) = queue.pop_front() {
      for &child in &[left_child[node], right_child[node]] {
        if child == -1 { continue; }
        let c = child as usize;
        if visited[c] { return false; }
        visited[c] = true;
        queue.push_back(c);
        count += 1;
      }
    }
    count == n
  }
}