⚡Flashcard Drill➔
NeetCode #458LC-1361MediumTrees
← Back to All Problems

#458 · #1361 · Validate Binary Tree Nodes(验证二叉树)

📌 Problem Statement & Constraints

You have n binary tree nodes numbered 0..n-1, given leftChild and rightChild arrays where -1 means no child. Return true if they form exactly one valid binary tree. Constraints: 1 <= n <= 10^4, leftChild.length == rightChild.length == n.

💡 Core Algorithmic Approaches

  1. A valid binary tree requires exactly one root (a node with no parent) and every other node to have exactly one parent.
  2. First verify parent uniqueness while counting roots: a node with two parents immediately fails.
  3. Then traverse from the unique root and check that all n nodes are reachable -- this catches cycles and disconnected components.
  4. The reachability check is what rules out a structure like a cycle with an extra dangling node.

💻 Benchmark Python3 Implementation

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        from collections import deque
        has_parent = [False] * n
        for i in range(n):
            for c in (leftChild[i], rightChild[i]):
                if c != -1:
                    if has_parent[c]:
                        return False       # a node has two parents
                    has_parent[c] = True
        roots = [i for i in range(n) if not has_parent[i]]
        if len(roots) != 1:
            return False                   # zero or multiple roots
        # traverse from the root and check full reachability
        seen = set()
        q = deque([roots[0]])
        while q:
            node = q.popleft()
            if node in seen:
                return False               # cycle
            seen.add(node)
            for c in (leftChild[node], rightChild[node]):
                if c != -1:
                    q.append(c)
        return len(seen) == n              # all nodes connected

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to check parents, one traversal.
💾 Space Complexity
O(n) for the bookkeeping arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking the root count: a graph can have one root and still contain a cycle elsewhere.
  • Skipping the reachability check: disconnected components would pass the parent test.
  • Forgetting the two-parent check: a node reached from two parents makes the structure a DAG, not a tree.
  • Assuming node 0 is the root: it need not be.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems