LeetCode 2764 - Is Array a Preorder of Some ‌Binary Tree

The problem asks us to determine whether a given list of nodes represents the preorder traversal of a binary tree. Each node is represented as a pair [id, parentId], where id is the unique identifier of the node, and parentId identifies its parent in the tree.

leetcodemediumstacktreedepth-first-searchbinary-tree

LeetCode Problem 2764

Difficulty: 🟡 Medium
Topics: Stack, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether a given list of nodes represents the preorder traversal of a binary tree. Each node is represented as a pair [id, parentId], where id is the unique identifier of the node, and parentId identifies its parent in the tree. A parentId of -1 indicates that the node is the root.

The key detail is that the nodes are given in a 0-indexed array, and we need to verify whether the array order corresponds to visiting the nodes in preorder traversal (root, left subtree, right subtree). We are not asked to reconstruct the tree, only to verify that the order is valid.

Constraints tell us that the number of nodes can be up to 100,000, so any solution must be linear or near-linear in time. Each node has a single parent, and the input guarantees that it forms a binary tree, so no node has more than two children. Edge cases include a single node tree, a skewed tree (all left or all right children), and nodes with consecutive children that could violate preorder ordering.

Approaches

A brute-force approach would involve reconstructing the tree explicitly using the parent-child relationships, then generating the preorder traversal and comparing it with the input array. While this is correct, it is too slow for large inputs due to tree reconstruction and traversal overhead, which can be O(n) in time but requires additional memory for node objects and child lists.

The key insight for an optimal solution is that preorder traversal can be validated using a stack approach similar to verifying preorder sequences of a binary search tree. For each node, we can track the most recent ancestors and ensure that no node violates the preorder property. In a binary tree, the children of a node appear consecutively, and the order in the input array allows us to simulate a stack of parent nodes and check whether each new node fits as a valid child of the current node.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Reconstruct the tree explicitly and check preorder sequence
Optimal O(n) O(n) Use a stack to simulate ancestors and validate preorder property without building the tree

Algorithm Walkthrough

  1. Initialize an empty stack stk to keep track of ancestors along the path from the root.
  2. Iterate through each node in the nodes array.
  3. For each node [id, parentId], repeatedly pop from the stack until the top of the stack matches parentId. This ensures the current node is a valid child of the topmost ancestor.
  4. If the stack becomes empty and the node is not the root (parentId != -1), the sequence is invalid; return false.
  5. Push the current node id onto the stack to represent the new ancestor path for subsequent nodes.
  6. If all nodes satisfy the stack checks, return true.

Why it works: The stack maintains the path from the root to the most recently visited node. In preorder traversal, after visiting a node, its children must follow consecutively. By popping nodes whose children are already visited, we ensure that each node’s parent is still on the stack. Any violation of this rule immediately indicates an invalid preorder sequence.

Python Solution

from typing import List

class Solution:
    def isPreorder(self, nodes: List[List[int]]) -> bool:
        if not nodes:
            return True
        
        stack = []
        
        for node_id, parent_id in nodes:
            while stack and stack[-1] != parent_id:
                stack.pop()
            if parent_id != -1 and (not stack or stack[-1] != parent_id):
                return False
            stack.append(node_id)
        
        return True

This Python implementation initializes a stack to track ancestors. For each node, it pops ancestors whose children have been processed, checks that the node’s parent is valid, and then appends the node to the stack. This directly follows the algorithm walkthrough and efficiently handles the preorder property.

Go Solution

func isPreorder(nodes [][]int) bool {
    stack := []int{}
    
    for _, node := range nodes {
        nodeID, parentID := node[0], node[1]
        
        for len(stack) > 0 && stack[len(stack)-1] != parentID {
            stack = stack[:len(stack)-1]
        }
        
        if parentID != -1 && (len(stack) == 0 || stack[len(stack)-1] != parentID) {
            return false
        }
        
        stack = append(stack, nodeID)
    }
    
    return true
}

In Go, the stack is represented by a slice. We pop elements by slicing and append new nodes as ancestors. The logic mirrors the Python implementation, accounting for Go’s slice handling.

Worked Examples

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

Node Stack Before Action Stack After
0,-1 [] root [0]
1,0 [0] parent valid [0,1]
2,0 [0,1] pop 1 [0,2]
3,2 [0,2] parent valid [0,2,3]
4,2 [0,2,3] pop 3 [0,2,4]

Returns true.

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

Node Stack Before Action Stack After
0,-1 [] root [0]
1,0 [0] parent valid [0,1]
2,0 [0,1] pop 1 [0,2]
3,1 [0,2] parent mismatch invalid

Returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is pushed and popped at most once
Space O(n) Stack stores ancestors; in worst case all nodes are in the stack

The algorithm is efficient enough for n <= 10^5.

Test Cases

# provided examples
assert Solution().isPreorder([[0,-1],[1,0],[2,0],[3,2],[4,2]]) == True  # true preorder
assert Solution().isPreorder([[0,-1],[1,0],[2,0],[3,1],[4,1]]) == False  # invalid preorder

# edge cases
assert Solution().isPreorder([[0,-1]]) == True  # single node tree
assert Solution().isPreorder([[0,-1],[1,0]]) == True  # simple left child
assert Solution().isPreorder([[0,-1],[1,0],[2,0]]) == True  # root with two children
assert Solution().isPreorder([[0,-1],[1,0],[2,1]]) == True  # left skewed
assert Solution().isPreorder([[0,-1],[1,0],[2,1],[3,2]]) == True  # deeper skewed
Test Why
[[0,-1],[1,0],[2,0],[3,2],[4,2]] Standard valid preorder sequence
[[0,-1],[1,0],[2,0],[3,1],[4,1]] Invalid preorder due to misplaced child
[[0,-1]] Single node tree edge case
[[0,-1],[1,0]] Simple root and left child
[[0,-1],[1,0],[2,0]] Root with two children
[[0,-1],[1,0],[2,1]] Left-skewed tree
[[0,-1],[1,0],[2,1],[3,2]] Deep skewed tree

Edge Cases

Single Node Tree: A tree with one node should always return true since a single root is trivially a valid preorder. The implementation handles this by starting with an empty stack and adding the root.

Skewed Tree: In a left or right skewed tree, all nodes are in a single line. The stack may grow to n elements in the worst case. The algorithm correctly maintains the parent-child relationship along the path.

Invalid Parent-Child Sequence: If a node appears out of order relative to its parent (like a right child appearing before its left subtree is fully traversed), the stack pop check detects the violation immediately and returns false, preventing incorrect assumptions about the tree structure.