Skip to content

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<vector<int>>& nodes) {
    stack<int> stack;  // Stores `id`s.

    for (const vector<int>& 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<List<Integer>> nodes) {
    Deque<Integer> stack = new ArrayDeque<>(); // Stores `id`s.

    for (List<Integer> 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 `id`s.

    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