We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Is Array a Preorder of Some ‌Binary Tree

Number: 2918

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a 0-indexed 2D integer array nodes where each element is of the form [id, parentId] (with parentId == -1 indicating the root), determine if the array represents the preorder traversal of some binary tree. In a preorder traversal we visit the current node first, then recursively traverse its left child followed by its right child. Although the input always forms a valid binary tree structure (each node having at most two children), the order in which they appear must match one possible preorder traversal.

Key Insights

  • The first node must be the root (its parentId must be -1).
  • In a preorder traversal, a node always appears before its children.
  • When moving to a new node in the sequence, it should either be the left child of the most recent node or be part of the right subtree of one of the ancestors.
  • A stack can simulate the DFS recursion: if the current node’s parent matches the top of the stack, it is the next child; otherwise, pop the stack until a match is found.
  • If no matching parent is found and the node’s parentId is not -1, the sequence cannot be a valid preorder.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(n) in the worst case, due to the auxiliary stack used in the simulation.

Solution

We simulate a preorder DFS traversal using a stack. We iterate over each node in the given sequence and check:

  1. For the first node, ensure its parentId is -1 (it must be the root).
  2. For every subsequent node:
    • If the top of the stack (which represents the current context in the DFS) has an id that matches the node’s parentId, then this node is a child of the current context.
    • Otherwise, pop from the stack because we are done processing the subtree and backtrack to a node that could be the parent.
    • If, after backtracking, no node’s id on the stack matches the node’s parentId (and the parentId is not -1), the sequence cannot represent a valid preorder traversal.
  3. Push the current node’s id onto the stack.

This process ensures that the given order adheres to the requirement that a node’s children appear consecutively after it in a valid preorder traversal of a binary tree.

Code Solutions

# Python solution with detailed comments
def isPreorderTraversal(nodes):
    # Initialize an empty list to use as a stack for DFS simulation.
    stack = []
    
    for idx, (node_id, parent_id) in enumerate(nodes):
        # For the root node, parent_id must be -1.
        if idx == 0:
            if parent_id != -1:
                return False
            stack.append(node_id)
        else:
            # Pop from the stack until the top matches the current node's parent_id.
            while stack and stack[-1] != parent_id:
                stack.pop()
            # If no parent is found, the ordering is invalid.
            if not stack:
                return False
            # Push the current node id onto the stack.
            stack.append(node_id)
    # If all nodes are processed correctly, return True.
    return True

# Example usage:
nodes1 = [[0,-1],[1,0],[2,0],[3,2],[4,2]]
print(isPreorderTraversal(nodes1))  # Expected output: True

nodes2 = [[0,-1],[1,0],[2,0],[3,1],[4,1]]
print(isPreorderTraversal(nodes2))  # Expected output: False
← Back to All Questions