# 2764. Is Array a Preorder of Some ‌Binary Tree¶

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: bool isPreorder(vector>& nodes) { stack stack; // Stores ids. for (const vector& node : nodes) { const int id = node[0]; const int parentId = node[1]; if (parentId == -1) { stack.push(id); continue; } while (!stack.empty() && stack.top() != parentId) stack.pop(); if (stack.empty()) return false; stack.push(id); } return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean isPreorder(List> nodes) { Deque stack = new ArrayDeque<>(); // Stores ids. for (List node : nodes) { final int id = node.get(0); final int parentId = node.get(1); if (parentId == -1) { stack.push(id); continue; } while (!stack.isEmpty() && stack.peek() != parentId) stack.pop(); if (stack.isEmpty()) return false; stack.push(id); } return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def isPreorder(self, nodes: List[List[int]]) -> bool: stack = [] # Stores ids. for id, parentId in nodes: if parentId == -1: stack.append(id) continue while stack and stack[-1] != parentId: stack.pop() if not stack: return False stack.append(id) return True