Valid Ordered Tree

Valid preorder tree

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

• parent set store the parentID

• Except root node, general node's parentID will be traversed and stored in parent set.

  boolean isPreorder(Node[] nodes){
    Set<Integer> parents = new HashSet<>();
    for(int i=0; i<nodes.size(); i++){
      if(nodes[i].parents != null){
        if(parents.contains(nodes[i].parentID)){
          parents.add(nodes[i].id);
        }else{
          return false;
        }
      }else{
        parents.add(nodes[i].id);
      }
    }
    return true;
  }

255. Verify Preorder BST

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

• Use a stack to store the traversed left tree, if p smaller than last pushed number, then we still in the left tree. Otherwise, pop all the node in stack if we are in right tree. Take the last poped number as upper bound

public boolean verifyPreorder(int[] preorder) {
    Stack<Integer> s = new Stack<>();
    int low = Integer.MIN_VALUE;
    for(int n: preorder){
        if(n < low) return false;
        // if n in right tree
        while( !s.isEmpty() && n > s.peek()){
            low = s.pop();
        }
        s.push(n);
    }
    return true;
}

331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #

• using a stack, scan left to right

  • case 1: we see a number, just push it to the stack

  • case 2: we see #, check if the top of stack is also #, if so, pop #, pop the number in a while loop, until top of stack is not #

• in the end, check if stack size is 1, and stack top is #

public boolean isValidSerialization(String preorder) {
    Stack<String> s = new Stack<>();
    for(String c: preorder.split(",")){
        while( c.equals("#") && !s.isEmpty() && s.peek().equals("#")){
            s.pop();
            if(s.isEmpty()) return false;
            s.pop();
        }
        s.push(c);
    }
    return s.size() == 1 && s.peek().equals("#");
}