Binary Search Tree

This is a simple data structure, but again one with which many of us may have not been familiar with in some time. But it seems to beloved of tech screeners (and very useful in networking software) so a refresher is always nice; I have here put together a simple sorted tree and some equally simple methods, both recursive and non-recursive for the main operations, which are:

• Insertion
• Finding nodes in the tree
• Displaying the tree

I created a class imaginatively called "BinarySearchTree" to implement this. In retrospect this constrcted my recursion to require helper methods, as I needed to pass the root node into the helper which was then treated as the "current" node and passed to future recursions. Not a big overhead, but a tad annoying. Here is the code:

First class is the TreeNode class, a simple class which assigns the identifier value upon construction.

  class TreeNode
 {
 public int nodeValue{get;set;}
 public TreeNode leftBranch, rightBranch;
 
 public TreeNode(int value)
 {
 nodeValue=value;
 leftBranch=null;
 rightBranch=null;
 }
 
 }

 

Then the BinarySearchTree class with Insert, Find and Display methods. This Display method does not show the nodes in order of value. Will make one of those next.

  class BinarySearchTree
 {
 TreeNode root = null;
 
 public BinarySearchTree(TreeNode rootNode)
 {
 root = rootNode;
 }
 
 public TreeNode Find(int keyValue)
 {
 TreeNode currentNode = root;
 
 while (currentNode != null)
 {
 if (currentNode.nodeValue == keyValue)
 {
 return currentNode;
 }
 else
 {
 if (keyValue < currentNode.nodeValue)
 {
 currentNode = currentNode.leftBranch;
 }
 if (keyValue > currentNode.nodeValue)
 {
 currentNode = currentNode.rightBranch;
 }
 }
 }
 
 return null;
 }
 
 public TreeNode FindRecursive(int keyValue)
 {
 return findRecursiveHelper(root, keyValue);
 }
 
 private TreeNode findRecursiveHelper(TreeNode current, int keyValue)
 {
 if (current == null)
 {
 return null;
 }
 
 if (current.nodeValue == keyValue)
 {
 return current;
 }
 
 if (keyValue < current.nodeValue)
 {
 if (current.leftBranch != null)
 {
 return (findRecursiveHelper(current.leftBranch, keyValue));
 }
 else
 {
 return null;
 }
 }
 
 if (keyValue > current.nodeValue)
 {
 if (current.rightBranch != null)
 {
 return (findRecursiveHelper(current.rightBranch, keyValue));
 }
 else
 {
 return null;
 }
 }
 
 return null;
 }
 
 
 public void Insert(TreeNode newNode)
 {
 InsertHelper(root, newNode);
 }
 
 private void InsertHelper(TreeNode current, TreeNode newNode)
 {
 if (newNode.nodeValue < current.nodeValue)
 {
 if (current.leftBranch == null)
 {
 current.leftBranch = newNode;
 }
 else
 {
 InsertHelper(current.leftBranch, newNode);
 }
 }
 if (newNode.nodeValue > current.nodeValue)
 {
 if (current.rightBranch == null)
 {
 current.rightBranch = newNode;
 }
 else
 {
 InsertHelper(current.rightBranch, newNode);
 }
 }
 }
 
 public void DisplayTree()
 {
 displayTreeHelper(root);
 }
 
 private void displayTreeHelper(TreeNode current)
 {
 Console.WriteLine(current.nodeValue.ToString());
 
 if (current.rightBranch != null)
 {
 displayTreeHelper(current.rightBranch);
 }
 
 if (current.leftBranch != null)
 {
 displayTreeHelper(current.leftBranch);
 }
 }
 }

 

To use the classes then I can call them from Main() as follows:

  BinarySearchTree bst = new BinarySearchTree(root);
 bst.Insert(new TreeNode(25));
 bst.Insert(new TreeNode(45));
 bst.Insert(new TreeNode(75));
 bst.Insert(new TreeNode(85));
 bst.Insert(new TreeNode(95));
 bst.Insert(new TreeNode(15));
 bst.Insert(new TreeNode(27));
 TreeNode tn = bst.Find(85);
 TreeNode trn = bst.FindRecursive(27);
 bst.DisplayTree();

 

As in the other articles the next things I need to ponder is, "If a candidate delivers this answer, what questions do we ask next?" Some potentials are:

1. Rewrite the Display method to display the nodes in order of values (in-order Traversal)
2. What optimisations can be applied to these trees?
   1. If using the tree to store data, then manipulation of regularly searched-for data to be acessible the top of a tree makes sense - extra points here for any mention of AVL, Red-black, treap etc...
3. and of course - what unit tests would you write
   1. which can be applied to every method in the classes