Is Is Array a Preorder of Some Binary Tree easy or hard?

The problem is rated Medium because it requires understanding preorder traversal properties and simulating them with a stack. The algorithm itself is linear, but identifying the ancestor backtracking logic can be tricky during interviews.

Is Array a Preorder of Some Binary Tree Python/Java solution

The implementation is identical across languages: iterate through the input, maintain a stack of ancestors, pop until the correct parent is found, and enforce the two‑children rule. The logic translates cleanly to Python, Java, C++, Go, and TypeScript using standard stack or list structures.

How to solve Is Array a Preorder of Some Binary Tree in O(n)?

Iterate through the array while maintaining a stack of the current ancestor path. For each (node, parent) pair, pop elements until the parent appears at the top of the stack. If the parent cannot be found, the preorder sequence is invalid. Track how many children each parent has and ensure it never exceeds two.

What is the best approach for Is Array a Preorder of Some Binary Tree?

The most efficient approach uses a stack to simulate the ancestor path of a preorder traversal. While scanning the array, pop nodes until the current parent is found, then attach the new node as its child. Track child counts to ensure no node exceeds two children. This approach runs in O(n) time and O(n) space.

Is Is Array a Preorder of Some Binary Tree asked at Google/Amazon/Meta?

Binary tree validation and preorder traversal problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving traversal validation, stack simulation, and ancestor tracking are common interview patterns.

What data structure is used in Is Array a Preorder of Some Binary Tree?

A stack is the key data structure. It represents the active path from the root to the current node during preorder traversal. Hash maps are often used alongside it to track parent relationships or the number of children each node has.

What is the time complexity of Is Array a Preorder of Some Binary Tree?

The optimal solution runs in O(n) time because each node is pushed and popped from the stack at most once. Space complexity is O(n) for the stack and auxiliary structures used to track child counts or parent relationships.

Description Hints 4 Solution Video 11:03

2764. Is Array a Preorder of Some ‌Binary Tree

Medium67.8% acceptancePremium elsewhere, free here

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 <= 10⁵
nodes[i].length == 2
0 <= nodes[i][0] <= 10⁵
-1 <= nodes[i][1] <= 10⁵
The input is generated such that nodes make a binary tree.

Topics

Hints open one at a time

Hint 1

Think of using the stack data structure.

Hint 2

Put the first node in the stack.

Hint 3

Iterate over the array and check if the node at the top of the stack is its parent; if it’s not, then pop the last element of the stack and check until you reach the parent of the current node in the array.

Hint 4

If the stack gets empty at any point, then the array is not the preorder.

11:03

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[0,-1],[1,0],[2,0],[3,2],[4,2]]

Input

[[0,-1],[1,0],[2,0],[3,1],[4,1]]

Your code is saved on this device.Solution