​​Lab 7: Binary Trees
​​Bard College – Computer Science – Data Structures
​​
​​In this lab we will build upon the Binary Search Tree data structures we have been discussing.

​​Tree Traversals

​​We will include four different tree traversal methods in the BST class. All the traversal methods should return a Queue​ of keys in the appropriate order.
​​
  • ​​Pre-Order Traversal: visit the root (of tree or sub-tree), then traverse the left sub-tree, and then traverse the right subtree
​​public Iterable<Key> preOrder()
​​private Iterable<Key> preOrder(Node x, Queue<Key> q)
  • ​​Post-Order Traversal: traverse the left sub-tree, then  traverse the right sub-tree, and then visit the root
​​public Iterable<Key> postOrder()
​​private Iterable<Key> postOrder(Node x,  Queue<Key> q)
  • ​​In-Order Traversal : traverse the left sub-tree, then visit the root, then  traverse the right sub-tree
​​public Iterable<Key> inOrder()
​​private Iterable<Key> inOrder(Node x,  Queue<Key> q)
  • ​​Level-Order Traversal: visit the root in level 0, then the nodes in level 1, then level 2, and so on
​​public Iterable<Key> levelOrder()
​​ 
​​echo "H E L L O W O R L D" | java BST
​​
​​PRE-ORDER
​​H 0
​​E 1
​​D 9
​​L 8
​​O 6
​​W 5
​​R 7
​​
​​POST-ORDER
​​D 9
​​E 1
​​R 7
​​W 5
​​O 6
​​L 8
​​H 0
​​
​​IN-ORDER
​​D 9
​​E 1
​​H 0
​​L 8
​​O 6
​​R 7
​​W 5
​​
​​LEVEL-ORDER
​​H 0