Interviews

Check Preorder

user profile image
System made a post.

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:
            st.append(nodes[i].ID)
            i += 1
        else:
            st.pop()
    return True


One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
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.


Free Consultation

aonecoding@gmail.com