Assignment 6

Consider the BTNode class: 
  
class BTNode<T> {
    T data;
    BTNode<T> left, right;
   
    public BTNode(T data){
        this.data = data;
        left = null;
        right = null;
    }
   
    public BTNode(T data, BTNode<T> left, BTNode<T> right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
Write each of the following functions without using recursion.
  1. static <T> T leftMost(BTNode<T> root): Returns the value stored in the left-most node.
  2. static <T> List<T> preorder(BTNode<T> root): Returns the pre-order traversal of a tree as a list.
  3. static <T> List<T> layer(BTNode<T> root, int n): Returns the values in layer n of a tree as a list. Assume that the root has layer 0.
  4. static <T> List<T> bfsOrder(BTNode<T> root): Returns the breadth-first traversal of a tree as a list.
  5. static <T extends Comparable<T>> boolean occurs(BTNode<T> root, T elm): Tests if a given value occurs in a binary search tree.
  6. static boolean wellFormed(String s): Tests if a given string of "([{}])" is properly well formed.