Is array a preorder of some binary tree

Stack Tree Depth-First Search Binary Tree

67.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_preorder(nodes: Vec<Vec<i32>>) -> bool {
    let mut stack: Vec<i32> = Vec::new();
    for node in &nodes {
      let id = node[0];
      let parent = node[1];
      while let Some(&top) = stack.last() {
        if top == parent { break; }
        stack.pop();
      }
      if parent == -1 {
        if !stack.is_empty() { return false; }
      } else if stack.is_empty() || *stack.last().unwrap() != parent {
        return false;
      }
      stack.push(id);
    }
    true
  }
}