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 the index i and 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.
Example 1:
Input: nodes = [[0,-1],[1,0],[2,0],[3,2],[4,2]] Output: true Explanation: The given nodes make the tree in the picture below. We can show that this is the preorder traversal of the tree, first we visit node 0, then we do the preorder traversal of the right child which is [1], then we do the preorder traversal of the left child which is [2,3,4].
Example 2:
Input: nodes = [[0,-1],[1,0],[2,0],[3,1],[4,1]] Output: false Explanation: The given nodes make the tree in the picture below. For the preorder traversal, first we visit node 0, then we do the preorder traversal of the right child which is [1,3,4], but we can see that in the given order, 2 comes between 1 and 3, so, it's not the preorder traversal of the tree.
Constraints:
1 <= nodes.length <= 105nodes[i].length == 20 <= nodes[i][0] <= 105-1 <= nodes[i][1] <= 105nodes make a binary tree.Problem Overview: You receive an array describing nodes and their parents in preorder order. The task is to verify whether this sequence could come from the preorder traversal of some binary tree where each node has at most two children and every child appears after its parent.
Approach 1: Explicit Tree Construction + DFS Validation (O(n) time, O(n) space)
Build the tree first, then check whether the preorder order matches the given array. Use a hash map from node value to its list of children. While building the structure, ensure no node receives more than two children and every parent appears before the child in the input. After constructing the adjacency list, run a Depth‑First Search preorder traversal and compare the produced sequence with the original array. This approach is straightforward but performs extra work because the full tree structure is built even though validation alone is enough.
Approach 2: Stack-Based Preorder Validation (O(n) time, O(n) space)
Preorder traversal always processes a node before exploring its children, and the traversal path behaves like a stack of ancestors. Maintain a stack representing the current path from the root to the latest node. For each pair (node, parent), pop nodes from the stack until the parent is found. If the parent never appears, the sequence cannot represent a valid preorder traversal. Track how many children each parent has to ensure the binary tree constraint (maximum two children). Push the current node onto the stack as the newest ancestor. This directly simulates preorder traversal rules without constructing the tree.
Approach 3: Parent Index Mapping + Ancestor Backtracking (O(n) time, O(n) space)
Maintain a map from node value to its index in the preorder array. While scanning the array, ensure every parent index is smaller than the child index, which enforces preorder ordering. Use a stack to represent the active ancestor chain and backtrack when the traversal moves to a different subtree. Child counters prevent any node from exceeding two children. This approach is similar to the stack simulation but emphasizes index validation to guarantee preorder constraints.
Recommended for interviews: The stack-based validation is the expected solution. It mirrors how preorder traversal behaves in a real binary tree, runs in O(n) time, and avoids unnecessary tree construction. Showing the explicit construction approach demonstrates understanding of traversal rules, but the stack simulation proves you can translate those rules into an efficient validation algorithm.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Tree Construction + DFS Validation | O(n) | O(n) | Good for understanding traversal correctness or when you need the actual tree structure. |
| Stack-Based Preorder Validation | O(n) | O(n) | Best general solution. Efficiently simulates preorder traversal without building the tree. |
| Parent Index Mapping + Ancestor Stack | O(n) | O(n) | Useful when validating ordering constraints using indices while still tracking ancestor relationships. |
【每日一题】LeetCode 2764. is Array a Preorder of Some Binary Tree • Huifeng Guan • 202 views views
Watch 1 more video solutions →Practice Is Array a Preorder of Some Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor