Is Array a Preorder of Some ‌Binary Tree

Is Array a Preorder of Some ‌Binary Tree - Problem

Given a 0-indexed integer 2D array nodes, your task is to determine if the given array represents the preorder traversal of some binary tree.

For each index i, nodes[i] = [id, parentId], where:

id is the id of the node at index i
parentId is the id of its parent in the tree (if the node has no parent, then parentId == -1)

Return true if the given array represents the preorder traversal of some tree, and false otherwise.

Note: The preorder traversal of a tree is a recursive way to traverse a tree in which we first visit the current node, then we do the preorder traversal for the left child, and finally, we do it for the right child.

Input & Output

Example 1 — Valid Preorder

$ Input: nodes = [[1,-1],[2,1],[3,2]]

› Output: true

💡 Note: This represents preorder traversal of tree: 1 is root, 2 is left child of 1, 3 is left child of 2. Preorder visits: 1 → 2 → 3, matching the input order.

Example 2 — Invalid Parent-Child

$ Input: nodes = [[1,-1],[2,1],[3,1],[4,2],[5,3]]

› Output: false

💡 Note: After visiting node 4 (child of 2), we cannot visit node 5 (child of 3) because we would have already finished the left subtree of 1. This violates preorder properties.

Example 3 — Multiple Roots

$ Input: nodes = [[1,-1],[2,-1]]

› Output: false

💡 Note: A binary tree can have only one root node. Having multiple nodes with parentId = -1 makes it invalid.

Constraints

0 ≤ nodes.length ≤ 10⁵
nodes[i].length == 2
1 ≤ id, parentId ≤ 10⁵
parentId == -1 if and only if the node is the root

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Parse parent-child relationships from nodes array

Preorder Property

Check if sequence follows preorder traversal rules

Validation Result

Return true if valid, false otherwise

Key Takeaway

🎯 Key Insight: Use stack to simulate preorder traversal - each node's parent must be at stack top when processing

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that in a valid preorder traversal, we must complete visiting all nodes in the left subtree before visiting any node in the right subtree. Best approach uses a stack simulation to validate the sequence in one pass. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Build Tree Then Validate	O(n²)	O(n)	Construct the complete binary tree, then perform preorder traversal to check if it matches the given sequence
Stack Simulation	O(n)	O(n)	Use stack to simulate preorder traversal and validate the sequence in one pass

Build Tree Then Validate — Algorithm Steps

Step 1: Build tree from parent-child relationships
Step 2: Perform preorder traversal on built tree
Step 3: Compare generated sequence with input order

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Relationships

Extract parent-child connections from input

Build Tree

Construct tree structure with proper links

Validate Order

Compare preorder traversal with input sequence

Code -

solution.c — C

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

#define MAX_NODES 1000

struct Node {
    int id;
    int children[2];
    int childCount;
};

int findNode(struct Node* nodes, int count, int id) {
    for (int i = 0; i < count; i++) {
        if (nodes[i].id == id) {
            return i;
        }
    }
    return -1;
}

void preorderTraversal(struct Node* nodes, int nodeCount, int nodeIndex, int* result, int* resultIndex) {
    if (nodeIndex == -1) return;
    
    result[(*resultIndex)++] = nodes[nodeIndex].id;
    
    for (int i = 0; i < nodes[nodeIndex].childCount; i++) {
        int childIndex = findNode(nodes, nodeCount, nodes[nodeIndex].children[i]);
        preorderTraversal(nodes, nodeCount, childIndex, result, resultIndex);
    }
}

bool solution(int nodes[][2], int nodeCount) {
    if (nodeCount == 0) return true;
    
    struct Node treeNodes[MAX_NODES];
    int treeNodeCount = 0;
    int root = -1;
    
    // Build tree structure
    for (int i = 0; i < nodeCount; i++) {
        int nodeId = nodes[i][0];
        int parentId = nodes[i][1];
        
        // Find or create node
        int nodeIndex = findNode(treeNodes, treeNodeCount, nodeId);
        if (nodeIndex == -1) {
            treeNodes[treeNodeCount].id = nodeId;
            treeNodes[treeNodeCount].childCount = 0;
            nodeIndex = treeNodeCount++;
        }
        
        if (parentId == -1) {
            if (root != -1) return false; // Multiple roots
            root = nodeIndex;
        } else {
            // Find or create parent
            int parentIndex = findNode(treeNodes, treeNodeCount, parentId);
            if (parentIndex == -1) {
                treeNodes[treeNodeCount].id = parentId;
                treeNodes[treeNodeCount].childCount = 0;
                parentIndex = treeNodeCount++;
            }
            
            if (treeNodes[parentIndex].childCount >= 2) {
                return false; // More than 2 children
            }
            
            treeNodes[parentIndex].children[treeNodes[parentIndex].childCount++] = nodeId;
        }
    }
    
    if (root == -1) return false;
    
    // Perform preorder traversal
    int expected[MAX_NODES];
    int expectedIndex = 0;
    preorderTraversal(treeNodes, treeNodeCount, root, expected, &expectedIndex);
    
    // Compare with input order
    if (expectedIndex != nodeCount) return false;
    
    for (int i = 0; i < nodeCount; i++) {
        if (expected[i] != nodes[i][0]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nodes[MAX_NODES][2];
    int nodeCount = 0;
    
    // Parse 2D array
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            nodes[nodeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            nodes[nodeCount][1] = atoi(ptr);
            nodeCount++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip closing bracket
        }
        ptr++;
    }
    
    bool result = solution(nodes, nodeCount);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Building tree takes O(n²) in worst case due to parent lookups, plus O(n) for traversal

⚠ Quadratic Growth

Space Complexity

O(n)

Tree structure and adjacency lists require O(n) space

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Build Tree Then Validate — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler