Check Preorder

Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder.

class Node:
    def __init__(self, ID, parent):
        self.ID = ID
        self.parentID = parent
        self.left = None
        self.right = None

#function to identify if given is preorder
Create a stack to store nodes in the current path when traversing.
Push node[i] into stack once node[i] is verified to be valid (valid only when parent of node[i] is in stack. 
In preorder a parent must show up earlier than its child)
Whenever stack top is not the parent of node[i], pop until parent of node[i] is at stack top. Push node[i].
If all nodes popped but parent of node[i] still not found, then node[i] is not in preorder sequence.
def isPreorder(nodes):
    if not nodes:
        return True
    st = [nodes[0].ID]
    i = 1
    while i < len(nodes):
        if not st:
            return False
        if st[-1] is nodes[i].parentID:
            i += 1
    return True

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.