Problem Description

You are given a 0-indexed 2D integer array nodes where each element nodes[i] = [id, parentId] represents:

• id: the identifier of the node at index i
• parentId: the identifier of its parent node (or -1 if the node has no parent, meaning it's the root)

Your task is to determine whether this array represents a valid preorder traversal of some binary tree.

In a preorder traversal, we:

1. First visit the current node
2. Then recursively traverse the left subtree
3. Finally recursively traverse the right subtree

The array nodes should follow this exact visiting order if it represents a valid preorder traversal.

Key Points:

• The nodes are listed in the order they would be visited during a preorder traversal
• Each node can have at most 2 children (since it's a binary tree)
• The root node has parentId = -1
• The array must represent exactly one complete binary tree

Example Understanding: If we have a tree like:

    1
   / \
  2   3

The preorder traversal would visit nodes in order: 1, 2, 3 So a valid input could be: [[1, -1], [2, 1], [3, 1]]

Return true if the given array represents a valid preorder traversal of some binary tree, and false otherwise.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a tree structure where nodes have parent-child relationships. A tree is a special type of graph (specifically, a connected acyclic graph).

Is it a tree?

• Yes: The problem explicitly mentions we're working with a binary tree. We have nodes with parent-child relationships, and we need to verify if the given array represents a valid preorder traversal of some binary tree.

DFS

• Conclusion: Since we're dealing with a tree problem, the flowchart leads us directly to DFS (Depth-First Search).

This makes perfect sense because:

1. Preorder traversal is inherently a depth-first traversal pattern (visit node, then recursively visit left subtree, then right subtree)
2. We need to traverse the tree structure following parent-child relationships
3. The solution validates the traversal order by using DFS to visit nodes in the expected preorder sequence

The DFS approach in the solution:

• Builds an adjacency list representation of the tree from the parent-child relationships
• Uses DFS to traverse starting from the root
• Verifies that nodes are visited in the exact order they appear in the input array
• Ensures all nodes are visited exactly once (validating it's a proper tree traversal)

Conclusion: The flowchart correctly identifies this as a tree problem that should be solved using DFS, which aligns perfectly with validating a preorder traversal sequence.

Intuition

The key insight is that if the array truly represents a preorder traversal, we should be able to reconstruct the traversal and verify it matches exactly with the given array.

Think about what a preorder traversal tells us:

1. The first element must be the root (since preorder visits root first)
2. For any node, its children appear in the array after it
3. The order of visiting is: parent → left child's subtree → right child's subtree

To verify if the given array is a valid preorder traversal, we can:

1. Build the tree structure from the parent-child relationships
2. Perform an actual preorder traversal
3. Check if our traversal matches the original array order

The clever part is that we don't need to explicitly build the tree. Instead, we can:

• Create an adjacency list where each parent points to its children
• Start DFS from the root (first element in the array)
• At each step of DFS, verify that the current node matches the expected node in the array at position k
• Increment k after visiting each node
• If at any point the current node doesn't match the expected node at position k, the array isn't a valid preorder
• After DFS completes, check if we've visited all nodes (k == len(nodes))

Why does this work? Because if the array is truly a preorder traversal:

• The nodes appear in the exact order they would be visited
• Our DFS will naturally follow the same order (parent → left → right)
• Any mismatch means the array doesn't represent a valid preorder sequence

The beauty of this approach is that we're essentially "replaying" the preorder traversal and verifying it step-by-step against the given array.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

Let's walk through the implementation step by step:

1. Build the Parent-Child Relationships:

g = defaultdict(list)
for i, p in nodes:
    g[p].append(i)

• We create an adjacency list g where each key is a parent ID and the value is a list of its children IDs
• For each [id, parentId] pair in the input, we add id as a child of parentId
• This gives us the tree structure to traverse

2. Initialize Traversal State:

k = 0

• k is a pointer that tracks our current position in the nodes array
• It represents which node we expect to visit next during our DFS

3. Define the DFS Function:

def dfs(i: int) -> int:
    nonlocal k
    if i != nodes[k][0]:
        return False
    k += 1
    return all(dfs(j) for j in g[i])

• The DFS function takes a node ID i as input
• First, it checks if the current node i matches the expected node at position k in the array (nodes[k][0])
• If they don't match, return False - the array isn't a valid preorder
• If they match, increment k to move to the next expected node
• Then recursively visit all children of node i using all(dfs(j) for j in g[i])
• The all() function ensures all children are successfully visited in order

4. Execute the Validation:

return dfs(nodes[0][0]) and k == len(nodes)

• Start DFS from the root node (nodes[0][0] - the first node in the array)
• After DFS completes, check two conditions:
  • The DFS returned True (all nodes matched their expected positions)
  • k == len(nodes) (we visited exactly all nodes, no more, no less)

Why This Works:

• The preorder traversal visits nodes in a specific order: root → left subtree → right subtree
• By iterating through children in the order they were added to g[i], we maintain the left-to-right order
• The global counter k ensures nodes are visited in the exact sequence given in the input
• If the input truly represents a preorder traversal, our DFS will visit nodes in the same order, and all checks will pass

Time Complexity: O(n) where n is the number of nodes - we visit each node once Space Complexity: O(n) for the adjacency list and recursion stack

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input: nodes = [[1, -1], [2, 1], [4, 2], [3, 1]]

This represents the following tree:

    1
   / \
  2   3
 /
4

Step 1: Build Parent-Child Relationships

g = defaultdict(list)

Processing each node:

• [1, -1]: Add 1 as child of -1 → g = {-1: [1]}
• [2, 1]: Add 2 as child of 1 → g = {-1: [1], 1: [2]}
• [4, 2]: Add 4 as child of 2 → g = {-1: [1], 1: [2], 2: [4]}
• [3, 1]: Add 3 as child of 1 → g = {-1: [1], 1: [2, 3], 2: [4]}

Step 2: Initialize and Start DFS

• Set k = 0 (pointing to first element in nodes array)
• Start DFS from root: dfs(1) (since nodes[0][0] = 1)

Step 3: DFS Traversal

1. Visit node 1 (k=0):

   • Check: nodes[0][0] = 1, current node = 1 ✓
   • Increment k → k=1
   • Visit children: [2, 3]

2. Visit node 2 (k=1):

   • Check: nodes[1][0] = 2, current node = 2 ✓
   • Increment k → k=2
   • Visit children: [4]

3. Visit node 4 (k=2):

   • Check: nodes[2][0] = 4, current node = 4 ✓
   • Increment k → k=3
   • No children, return True

4. Back to node 1, visit node 3 (k=3):

   • Check: nodes[3][0] = 3, current node = 3 ✓
   • Increment k → k=4
   • No children, return True

Step 4: Final Validation

• DFS returns True (all nodes matched)
• Check k == len(nodes): 4 == 4 ✓
• Result: True - this is a valid preorder traversal!

Counter-example: If the input was [[1, -1], [3, 1], [2, 1], [4, 2]]:

• When we visit node 1's children [2, 3], we'd visit 2 first
• But nodes[1][0] = 3, not 2
• The check would fail, returning False

This demonstrates how the algorithm verifies that nodes appear in the exact order they would be visited during a preorder traversal.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes.

• Building the adjacency list g takes O(n) time as we iterate through all nodes once.
• The DFS traversal visits each node exactly once. At each node, we:
  • Check if the current index matches nodes[k][0] in O(1) time
  • Increment k in O(1) time
  • Recursively call DFS for all children
• Since each node is visited once and each edge is traversed once, the total time for DFS is O(n).
• The final check k == len(nodes) takes O(1) time.
• Overall: O(n) + O(n) + O(1) = O(n)

Space Complexity: O(n)

• The adjacency list g stores all parent-child relationships, which takes O(n) space in the worst case (each node except the root has one parent).
• The recursive call stack depth can be up to O(n) in the worst case when the tree is completely unbalanced (essentially a linked list).
• The variable k takes O(1) space.
• Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Validating Root Node Position

A common mistake is assuming the root node (with parentId = -1) must be at index 0. While the problem states nodes are in preorder traversal order, failing to verify this can lead to incorrect results.

Pitfall Example:

# Incorrect: Doesn't check if first node is actually the root
def isPreorder(self, nodes: List[List[int]]) -> bool:
    # ... build adjacency list ...
    return dfs(nodes[0][0])  # Assumes first node is root

Solution:

# Correct: Verify the first node has parentId = -1
def isPreorder(self, nodes: List[List[int]]) -> bool:
    if not nodes or nodes[0][1] != -1:
        return False  # First node must be root
    # ... rest of the implementation ...

2. Binary Tree Constraint Violation

The code doesn't explicitly check if each node has at most 2 children. A node with 3+ children would make it not a binary tree, but the current implementation might still return True.

Pitfall Example:

# Current code doesn't validate binary tree constraint
adjacency_list[parent_id].append(node_id)  # Could add 3+ children

Solution:

# Add validation for binary tree constraint
adjacency_list = defaultdict(list)
for node_id, parent_id in nodes:
    adjacency_list[parent_id].append(node_id)
    if len(adjacency_list[parent_id]) > 2:
        return False  # More than 2 children - not a binary tree

3. Duplicate Node IDs

The implementation doesn't check for duplicate node IDs, which would indicate an invalid tree structure.

Pitfall Example:

# Input: [[1, -1], [2, 1], [2, 1]]  # Node 2 appears twice
# Current code might not catch this error

Solution:

def isPreorder(self, nodes: List[List[int]]) -> bool:
    seen_nodes = set()
    adjacency_list = defaultdict(list)
  
    for node_id, parent_id in nodes:
        if node_id in seen_nodes:
            return False  # Duplicate node ID detected
        seen_nodes.add(node_id)
        adjacency_list[parent_id].append(node_id)
    # ... rest of implementation ...

4. Multiple Root Nodes

The code doesn't explicitly check if there's exactly one root node. Multiple nodes with parentId = -1 would create a forest instead of a single tree.

Solution:

def isPreorder(self, nodes: List[List[int]]) -> bool:
    root_count = sum(1 for _, parent_id in nodes if parent_id == -1)
    if root_count != 1:
        return False  # Must have exactly one root
    # ... rest of implementation ...

5. Disconnected Components

If a node references a parent that doesn't exist in the tree, it creates a disconnected component.

Pitfall Example:

# Input: [[1, -1], [2, 1], [3, 99]]  # Node 99 doesn't exist

Solution:

def isPreorder(self, nodes: List[List[int]]) -> bool:
    all_node_ids = {node_id for node_id, _ in nodes}
  
    for node_id, parent_id in nodes:
        if parent_id != -1 and parent_id not in all_node_ids:
            return False  # Parent doesn't exist
    # ... rest of implementation ...

Complete Robust Solution:

def isPreorder(self, nodes: List[List[int]]) -> bool:
    if not nodes or nodes[0][1] != -1:
        return False
  
    seen_nodes = set()
    all_node_ids = {node_id for node_id, _ in nodes}
    adjacency_list = defaultdict(list)
    root_count = 0
  
    for node_id, parent_id in nodes:
        # Check for duplicate nodes
        if node_id in seen_nodes:
            return False
        seen_nodes.add(node_id)
      
        # Count roots
        if parent_id == -1:
            root_count += 1
            if root_count > 1:
                return False
      
        # Check parent exists
        elif parent_id not in all_node_ids:
            return False
      
        # Build adjacency list and check binary tree constraint
        adjacency_list[parent_id].append(node_id)
        if len(adjacency_list[parent_id]) > 2:
            return False
  
    # Original DFS validation
    current_index = 0
  
    def dfs(node_id: int) -> bool:
        nonlocal current_index
        if node_id != nodes[current_index][0]:
            return False
        current_index += 1
        return all(dfs(child) for child in adjacency_list[node_id])
  
    return dfs(nodes[0][0]) and current_index == len(nodes)