in C# Add a method to the binary search tree class that returns false if the value passed into the method is not in the tree. If the value is in tree, then return true plus the values on either side of the value. In other words, if the value is in the tree, return true plus set the left reference variable to the closest value in the tree the is less than value and set the right reference variable to the closest value in the tree that is greater than value.

The first line of the method is: public bool ReturnEnds(T value, ref T left, ref T right)

Example:

15 5 50 45 95 where this tree is a variable called aBst

aBst.ReturnEnds(15, ref l, ref r) returns true and l=5, r=45 aBst.ReturnEnds(50, ref l, ref r) returns true and l=45, r=95 aBst.ReturnEnds(9, ref l, ref r) returns false aBst.ReturnEnds(5, ref l, ref r) returns true and l=5, r=5 // if there are no children on a side, return the value passed into the method

using System; using System.Collections.Generic;

/* Student Version */

public class BinSearchTree where T : IComparable { private class Node // shown in class { public T Data { get; set; } public Node Left;// { get; set; } public Node Right; // { get; set; } public Node(T d = default(T), Node leftnode = null, Node rightnode = null) { Data = d; Left = leftnode; Right = rightnode; }

public override string ToString() { return Data.ToString(); } }

private Node root; public BinSearchTree() { root = null; } public virtual void Clear() { root = null; }

public T FindMinNR() { if (root == null) throw new ApplicationException("Can find min on empty tree"); else { Node pTmp = root; while (pTmp.Left != null) pTmp = pTmp.Left; return pTmp.Data; } } public T FindMin() { if (root == null) throw new ApplicationException("FindMin called on empty BinSearchTree"); else return FindMin(root); } private T FindMin(Node pTmp) { if (pTmp.Left == null) return pTmp.Data; else return FindMin(pTmp.Left); }

public T Find(T value) { return Find(value, root); } private T Find(T value, Node pTmp) { if (pTmp == null) throw new ApplicationException("BinSearchTree could not find " + value); // Item not found else if (value.CompareTo(pTmp.Data) < 0) // value < pTmp.Data return Find(value, pTmp.Left); // search left subtree else if (value.CompareTo(pTmp.Data) > 0) // value > pTmp.Data return Find(value, pTmp.Right); // search right subtree else return pTmp.Data; // Found it }

public bool TryFind(ref T value) { Node pTmp = root; int result; while (pTmp != null) { result = value.CompareTo(pTmp.Data); if (result == 0) { // found it value = pTmp.Data; return true; } else if (result < 0) // value < pTmp.Data, search left subtree pTmp = pTmp.Left; else if (result > 0) // value > pTmp.Data, search right subtree pTmp = pTmp.Right; } return false; // didn't find it } public void Insert(T newItem) { root = Insert(newItem, root); } private Node Insert(T newItem, Node pTmp) { if (pTmp == null) return new Node(newItem, null, null); else if (newItem.CompareTo(pTmp.Data) < 0) // newItem < pTmp.Data pTmp.Left = Insert(newItem, pTmp.Left); else if (newItem.CompareTo(pTmp.Data) > 0) // newItem > pTmp.Data pTmp.Right = Insert(newItem, pTmp.Right); else // Duplicate throw new ApplicationException("Tree did not insert " + newItem + " since an item with that value is already in the tree");

return pTmp; }

public void Remove(T value) { Remove(value, ref root); } private void Remove(T value, ref Node pTmp) { if (pTmp == null) throw new ApplicationException("BinSearchTree could not remove " + value); // Item not found else if (value.CompareTo(pTmp.Data) < 0) // value < pTmp.Data Remove(value, ref pTmp.Left); else if (value.CompareTo(pTmp.Data) > 0) // value > pTmp.Data Remove(value, ref pTmp.Right); else if (pTmp.Left != null && pTmp.Right != null) // Two children { pTmp.Data = FindMin(pTmp.Right); Remove(pTmp.Data, ref pTmp.Right); } else pTmp = (pTmp.Left != null) ? pTmp.Left : pTmp.Right; } public bool TryInsert(T value) { if (root == null) root = new Node(value, null, null); else { Node pTmp = root, parent; while (pTmp != null) { parent = pTmp; if (value.CompareTo(pTmp.Data) == 0) // trying to insert duplicate key return false; else if (value.CompareTo(pTmp.Data) < 0) // value < pTmp.Data, search left subtree { pTmp = pTmp.Left; if (pTmp == null) parent.Left = new Node(value, null, null); } else // value > pTmp.Data, search right subtree { pTmp = pTmp.Right; if (pTmp == null) parent.Right = new Node(value, null, null); } } } return true; }

public bool Contains(T value) { throw new NotImplementedException("BST Contains not implemented"); }

public T FindMax() { return FindMax(root).Data; } private Node FindMax(Node pTmp) { if (pTmp == null) throw new ApplicationException("FindMax called on empty BinSearchTree"); if (pTmp.Right == null) return pTmp; return FindMax(pTmp.Right); }

public T FindMin() { return FindMin(root).Data; } private Node FindMin(Node pTmp) { if (pTmp == null) throw new ApplicationException("FindMin called on empty BinSearchTree"); if (pTmp.Left == null) return pTmp; return FindMax(pTmp.Left); } }