I want you to implement an In Order, Post Order and Pre Order, and Breadth First traversal that output a string of the entire tree. The four functions are in the BST.cs file Its up to you to test this and see how it works (see the slides theres a handy one). Secondly, I want you to implement a simple FindSmallest, recursively, that well, finds the smallest element in the tree (the very leftmost element in the tree).

Here is the code:

namespace BinarySearchTreeLab { class Node { public int value; public Node left; public Node right; }

class BinarySearchTree { public Node insert(Node root, int v) { if (root == null) { root = new Node(); root.value = v; }

// insertion logic, if the value (v )is < root, insert to the root.left // otherwise it's >=, so insert to the right else if (v < root.value) { root.left = insert(root.left, v); } else { root.right = insert(root.right, v); }

return root; } // Lab: Take the code from here, and implement 3 different traversals as strings // public string traverse (Node root)

public void traverse(Node root) { if (root == null) { return; } Console.WriteLine( root.value.ToString()); traverse(root.left); traverse(root.right);

} // For students to implement in the lab // note that in order, pre order and post order are all just rearranging the order // of the traverse method basically public string inOrder(Node root) { return ""; }

public string preOrder(Node root) { return ""; }

public string postOrder(Node root) { return ""; }

public string breadthFirst(Node root) { return ""; }

}

class BinarySearch { static void Main(string[] args) { Node root = null; BinarySearchTree bst = new BinarySearchTree(); int SIZE = 10; // tested on up to 200k elements and it works fine int[] testArray = new int[SIZE]; Random rnd = new Random(); Console.WriteLine("Elements to be inserted into the BST"); for (int i=0; i

Console.WriteLine();

Console.ReadKey(); } }

}