in c#

using System; using System.Collections.Generic; public class BinSearchTree where T : IComparable { private class Node { public T Data { get; set; } public Node Left; public Node Right; 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); else if (value.CompareTo(pTmp.Data) 0) return Find(value, pTmp.Right); else return pTmp.Data; } public bool TryFind(ref T value) { Node pTmp = root; int result; while (pTmp != null) { result = value.CompareTo(pTmp.Data); if (result == 0) { value = pTmp.Data; return true; } else if (result 0) pTmp = pTmp.Right; } return false; } 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) pTmp.Right = Insert(newItem, pTmp.Right); else 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); else if (value.CompareTo(pTmp.Data) 0) Remove(value, ref pTmp.Right); else if (pTmp.Left != null && pTmp.Right != null) { 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) return false; else if (value.CompareTo(pTmp.Data) 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 I left, ref T right) Example: 15 5 50 45 95 where this tree is a variable called aBst aBst.ReturnEnds(15, ref I, ref r) returns true and I=5, r=45 aBst.ReturnEnds(50, ref I, refr) returns true and I=45, r=95 aBst.ReturnEnds(9, ref I, ref r) returns false aBst.ReturnEnds(5, ref I, ref r) returns true and l=5, r=5 // if there are no children on a side, return the value passed into the method 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 I left, ref T right) Example: 15 5 50 45 95 where this tree is a variable called aBst aBst.ReturnEnds(15, ref I, ref r) returns true and I=5, r=45 aBst.ReturnEnds(50, ref I, refr) returns true and I=45, r=95 aBst.ReturnEnds(9, ref I, ref r) returns false aBst.ReturnEnds(5, ref I, ref r) returns true and l=5, r=5 // if there are no children on a side, return the value passed into the method