Validate Binary Tree Nodes

medium tree dfs bfs graph union find binary tree

Problem

n nodes labeled 0..n-1; leftChild[i] and rightChild[i] give the children of node i (-1 if none). Return true if these form exactly one valid binary tree.

Inputn = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]

Outputtrue

Node 0 is root with children 1 and 2; node 2 has child 3.

leftChild

rightChild

def validate_binary_tree_nodes(n, leftChild, rightChild):
    indeg = [0] * n
    for c in leftChild + rightChild:
        if c != -1:
            indeg[c] += 1
            if indeg[c] > 1: return False
    roots = [i for i in range(n) if indeg[i] == 0]
    if len(roots) != 1: return False
    seen, stk = {roots[0]}, [roots[0]]
    while stk:
        u = stk.pop()
        for c in (leftChild[u], rightChild[u]):
            if c != -1:
                if c in seen: return False
                seen.add(c); stk.append(c)
    return len(seen) == n

function validateBinaryTreeNodes(n, leftChild, rightChild) {
  const indeg = new Array(n).fill(0);
  for (const c of leftChild.concat(rightChild)) {
    if (c !== -1) { indeg[c]++; if (indeg[c] > 1) return false; }
  }
  let root = -1;
  for (let i = 0; i < n; i++) if (indeg[i] === 0) { if (root !== -1) return false; root = i; }
  if (root === -1) return false;
  const seen = new Set([root]); const stk = [root];
  while (stk.length) {
    const u = stk.pop();
    for (const c of [leftChild[u], rightChild[u]]) {
      if (c !== -1) { if (seen.has(c)) return false; seen.add(c); stk.push(c); }
    }
  }
  return seen.size === n;
}

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indeg = new int[n];
        for (int c : leftChild) if (c != -1 && ++indeg[c] > 1) return false;
        for (int c : rightChild) if (c != -1 && ++indeg[c] > 1) return false;
        int root = -1;
        for (int i = 0; i < n; i++) if (indeg[i] == 0) { if (root != -1) return false; root = i; }
        if (root == -1) return false;
        Set seen = new HashSet<>(); seen.add(root);
        Deque st = new ArrayDeque<>(); st.push(root);
        while (!st.isEmpty()) {
            int u = st.pop();
            for (int c : new int[]{leftChild[u], rightChild[u]}) if (c != -1) {
                if (!seen.add(c)) return false;
                st.push(c);
            }
        }
        return seen.size() == n;
    }
}

bool validateBinaryTreeNodes(int n, vector& leftChild, vector& rightChild) {
    vector indeg(n, 0);
    for (int c : leftChild) if (c != -1 && ++indeg[c] > 1) return false;
    for (int c : rightChild) if (c != -1 && ++indeg[c] > 1) return false;
    int root = -1;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) { if (root != -1) return false; root = i; }
    if (root == -1) return false;
    vector seen(n, false); seen[root] = true;
    stack st; st.push(root);
    int cnt = 1;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int c : {leftChild[u], rightChild[u]}) if (c != -1) {
            if (seen[c]) return false;
            seen[c] = true; cnt++; st.push(c);
        }
    }
    return cnt == n;
}

Explanation

A valid binary tree has three properties, and the solution checks each one: there is exactly one root, every other node has exactly one parent, and all nodes are reachable from the root with no cycles.

First we count in-degree — how many times each node appears as someone's child. If any node has in-degree greater than 1, it has two parents, which is illegal, so we return false right away.

Next we find the root: the unique node with in-degree 0. If there isn't exactly one such node, the structure can't be a single tree, so we fail.

Finally we walk the tree from the root using a stack (DFS), adding each child to a seen set. If we ever revisit a node already in seen, there's a cycle. At the end, the tree is valid only if every node was reached, i.e. seen.size === n.

Example: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]. Node 0 has in-degree 0 (the root), its children 1 and 2 each have one parent, and node 2's child 3 is reachable — all 4 nodes seen, so the answer is true.

Time: O(n) Space: O(n)