​​Lab 9: Binary Trees
​​Bard College – Computer Science – Data Structures
​​
​​In this lab we will build upon the Binary Search Tree data structure we studied this week in class.
​​

​​Tree Traversals

​​Add four different tree traversal methods to 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