Below is the syntax highlighted version of LevelOrder.java
from §3.2 Binary Search Trees.
/****************************************************************************** * Compilation: javac LevelOrder.java * Execution: java LevelOrder < level.txt * Dependencies: In.java StdOut.java * * Construct a BST based on its level order traversal or report * that the level-order traversal did not come from a BST. * * Note: takes linearithmic time. * * % java LevelOrder * T C F A D E G Z * has duplicate keys = false * level order of some BST = false * level order of some red-black BST = false * * % T C Z A F D G E * has duplicate keys = false * level order of some BST = true * level order of some red-black BST = false * * % java LevelOrder * T C W A E U X D * has duplicate keyes = false * level order of some BST = true * level order of some red-black BST = true * red links = D * * Here is a linear-time algorithm. Create a Node data type where each Node stores a key, * a left child, a right child, and an interval (k1, k2) of keys that are permitted in its subtree. * * Maintain two queues, one of keys and the other of nodes. * - Initialize queue 1 to all of the keys in the level-order traversal, in that order. * - Initialize queue 2 to a new Node containing the interval (-infinity, +infinity) * Repeat * - Dequeue the next key k from queue 1. * - Repeatedly dequeue the next Node from queue 2 until key k is consistent with * the interval in node x, i.e., k1 < k < k2. * (If no such node, then level-order does not correspond to any BST.) * - Assign k as the key in node x; create a left child of x with interval (k1, k); * and a right child of x with interval (k, k2); enqueue both Nodes. * * The BST is the subset of Nodes that get assigned keys (you can think of the Nodes * with no keys as null). * ******************************************************************************/ import java.util.Iterator; public class LevelOrder<Key extends Comparable<Key>> { private static final boolean RED = true; private static final boolean BLACK = false; private Iterable<Key> level; private Node root; private int n; // from level-order traversal public LevelOrder(Iterable<Key> level) { Queue<Key> queue = new Queue<Key>(); for (Key key : level) queue.enqueue(key); this.n = queue.size(); this.level = level; root = construct(queue); } private Node construct(Queue<Key> queue) { if (queue.size() == 0) return null; Key key = queue.dequeue(); Node x = new Node(key); Queue<Key> left = new Queue<Key>(); Queue<Key> right = new Queue<Key>(); while (!queue.isEmpty()) { Key s = queue.dequeue(); if (s.compareTo(key) < 0) left.enqueue(s); else if (s.compareTo(key) > 0) right.enqueue(s); } x.left = construct(left); x.right = construct(right); return x; } private class Node { private Key key; // sorted by key private Node left, right; // left and right subtrees private boolean color; // color private int bh; // black height private Node(Key key) { this.key = key; this.color = BLACK; this.bh = 0; } } public boolean hasDuplicateKeys() { return n != size(root); } public boolean isBST() { if (hasDuplicateKeys()) return false; // iterators have same size // check if input level order = level order of tree constructed Iterator<Key> iterator1 = level.iterator(); Iterator<Key> iterator2 = levelOrder().iterator(); for (int i = 0; i < n; i++) { Key key1 = iterator1.next(); Key key2 = iterator2.next(); if (!key1.equals(key2)) return false; } assert hasSymmetricOrder(); return true; } // black height private int bh(Node x) { if (x == null) return -1; return x.bh; } // determine colors, as forced private boolean isRedBlackBST() { return isBST() && isRedBlackBST(root); } private boolean isRedBlackBST(Node x) { if (x == null) return true; boolean b1 = isRedBlackBST(x.left); boolean b2 = isRedBlackBST(x.right); if (!b1 || !b2) return false; if (bh(x.left) == bh(x.right)) { x.bh = 1 + bh(x.left); return true; } else if (bh(x.left) == bh(x.right) + 1) { x.left.color = RED; x.bh = bh(x.left); return true; } else return false; } // return red links public Iterable<Key> redLinks() { Queue<Key> keys = new Queue<Key>(); redLinks(root, keys); return keys; } private void redLinks(Node x, Queue<Key> keys) { if (x == null) return; redLinks(x.left, keys); if (x.color == RED) keys.enqueue(x.key); redLinks(x.right, keys); } // does this binary tree satisfy symmetric order? private boolean hasSymmetricOrder() { return hasSymmetricOrder(root, null, null); } // is the tree rooted at x a BST with all keys strictly between min and max // (if min or max is null, treat as empty constraint) private boolean hasSymmetricOrder(Node x, Key min, Key max) { if (x == null) return true; if (min != null && x.key.compareTo(min) <= 0) return false; if (max != null && x.key.compareTo(max) >= 0) return false; return hasSymmetricOrder(x.left, min, x.key) && hasSymmetricOrder(x.right, x.key, max); } private int size(Node x) { if (x == null) return 0; return 1 + size(x.left) + size(x.right); } // level-order traversal of BST public Iterable<Key> levelOrder() { Queue<Key> keys = new Queue<Key>(); Queue<Node> queue = new Queue<Node>(); queue.enqueue(root); while (!queue.isEmpty()) { Node x = queue.dequeue(); if (x == null) continue; keys.enqueue(x.key); queue.enqueue(x.left); queue.enqueue(x.right); } return keys; } /*************************************************************************** * Test client. ***************************************************************************/ public static void main(String[] args) { Queue<String> queue = new Queue<String>(); while (!StdIn.isEmpty()) queue.enqueue(StdIn.readString()); LevelOrder<String> level = new LevelOrder<String>(queue); StdOut.println("has duplicate keys = " + level.hasDuplicateKeys()); StdOut.println("level order of some BST = " + level.isBST()); StdOut.println("level order of some red-black BST = " + level.isRedBlackBST()); if (level.isRedBlackBST()) { StdOut.print("red links = "); for (String s : level.redLinks()) StdOut.print(s + " "); StdOut.println(); } } }