Validate Binary Tree Nodes - Practice Coding Problems

Validate Binary Tree Nodes - Problem

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: The nodes have no values and we only use the node numbers in this problem.

Input & Output

Example 1 — Valid Tree

$ Input: leftChild = [1,-1,0,-1], rightChild = [-1,2,-1,-1]

› Output: true

💡 Note: Node 0 is root, has left child 1. Node 1 has right child 2. Node 2 has left child 0 (cycle). Actually this forms: 0->1, 1->2, 2->0, which is a cycle, so should be false. Let me correct: Node 0 has left=1, Node 1 has right=2, Node 2 has left=0. This creates a cycle.

Example 2 — Multiple Roots

$ Input: leftChild = [1,0,3,-1], rightChild = [-1,-1,-1,-1]

› Output: false

💡 Note: Nodes 0 and 1 point to each other as children, creating a cycle. Also node 2 has no parent, creating multiple components.

Example 3 — Simple Valid Tree

$ Input: leftChild = [1,2,-1,-1], rightChild = [-1,-1,-1,-1]

› Output: true

💡 Note: Node 0 is root with left child 1. Node 1 has left child 2. Forms valid tree: 0->1->2

Constraints

n == leftChild.length == rightChild.length
1 ≤ n ≤ 10⁴
-1 ≤ leftChild[i], rightChild[i] ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

leftChild and rightChild arrays define parent-child relationships

Validation

Check for single root, no multiple parents, and connectivity

Result

Return true if forms valid binary tree, false otherwise

Key Takeaway

🎯 Key Insight: A valid binary tree has exactly one root and forms a connected acyclic structure

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is that a valid binary tree must have exactly one root (node with no parent), no node can have multiple parents, and all nodes must be connected. Best approach uses single pass validation with parent counting and DFS connectivity check. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Validation	O(n)	O(n)	Validate all properties in one traversal
Brute Force Validation	O(n)	O(n)	Check all validation rules separately

Single Pass Validation — Algorithm Steps

Build parent count array while detecting duplicates
Find unique root node
DFS from root to verify all nodes reachable

Visualization

Tap to expand

Step-by-Step Walkthrough

Build & Validate

Count parents while detecting violations

Find Root

Identify single root node

DFS Check

Verify all nodes connected to root

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void dfs(int node, int* leftChild, int* rightChild, bool* visited, int n) {
    if (node == -1 || node >= n || visited[node]) return;
    visited[node] = true;
    dfs(leftChild[node], leftChild, rightChild, visited, n);
    dfs(rightChild[node], leftChild, rightChild, visited, n);
}

bool solution(int* leftChild, int* rightChild, int n) {
    if (n == 0) return true;
    
    // Build parent count and detect multiple parents
    int* parentCount = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        if (leftChild[i] != -1) {
            parentCount[leftChild[i]]++;
            if (parentCount[leftChild[i]] > 1) {
                free(parentCount);
                return false;
            }
        }
        if (rightChild[i] != -1) {
            parentCount[rightChild[i]]++;
            if (parentCount[rightChild[i]] > 1) {
                free(parentCount);
                return false;
            }
        }
    }
    
    // Find root
    int root = -1;
    for (int i = 0; i < n; i++) {
        if (parentCount[i] == 0) {
            if (root != -1) {
                free(parentCount);
                return false; // Multiple roots
            }
            root = i;
        }
    }
    
    if (root == -1) {
        free(parentCount);
        return false; // No root
    }
    
    // DFS to check connectivity
    bool* visited = (bool*)calloc(n, sizeof(bool));
    dfs(root, leftChild, rightChild, visited, n);
    
    int visitedCount = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) visitedCount++;
    }
    
    free(parentCount);
    free(visited);
    return visitedCount == n;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int leftChild[1000], n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        leftChild[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    int rightChild[1000];
    int idx = 0;
    token = strtok(line, "[],\n ");
    while (token != NULL && idx < n) {
        rightChild[idx++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(leftChild, rightChild, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count parents plus DFS traversal

✓ Linear Growth

Space Complexity

O(n)

Parent count array and recursion stack

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Validation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler