C# - Binary Search Tree Contains/Is Present Method

I'm really struggling to get this method to work, I was wondering if you could help me out. I've been using the ref keyword, so I'll keep using it. I've been searching the web and it's been some help, but I've tried everything I can possibly think of. Both my count and height methods work, however, I'm just really struggling to get this Contain method to work. Many examples on the web have showed both a public and private method of contains (I understand as to why) but I'm sure it could be done within one method? Surely, right? Also, please ignore the RemoveItem method, unless you wish to give me a head-start, that's at your discretion. I know it's tricky as I've looked up on it earlier during the week.

Node class-

class Node<T> where T : IComparable

private T data;
public Node<T> Left, Right;

public Node(T item)

data = item;
Left = null;
Right = null;

public T Data

set data = value;
get return data;





BinTree Class-

class BinTree<T> where T : IComparable

protected Node<T> root;

public BinTree() //creates an empty tree

root = null;

public BinTree(Node<T> node) //creates a tree with node as the root

root = node;

//I've deleted my preOrder, inOrder and postOrder methods just to save you some time




BSTree Class-

class BSTree<T> : BinTree<T> where T : IComparable

public BSTree()

root = null;


private void insertItem(T item, ref Node<T> tree)

if (tree == null)

tree = new Node<T>(item);



else if (item.CompareTo(tree.Data) < 0)

insertItem(item, ref tree.Left);


else if (item.CompareTo(tree.Data) > 0)
insertItem(item, ref tree.Right);


public void InsertItem(T item)

insertItem(item, ref root);


public int Height(ref Node<T> tree)
//Return the max level of the tree

if (tree == null)

return 0;
return (1 + Math.Max(Height(ref tree.Left), Height(ref tree.Right)));



public int Count(ref Node<T> tree)
//Return the number of nodes in the tree

int counter = 0;

if (tree == null)

return 0;

else if (tree.Left != null)

counter += Count(ref tree.Left);
counter++;


if (tree.Right != null)

counter += Count(ref tree.Right);
counter++;

return counter;




public Boolean Contains(T item, ref Node<T> tree)
//Return true if the item is contained in the BSTree, false //otherwise.

if (tree == null)

return false;




if (item.CompareTo(tree.Data) < 0)

return Contains(ref tree.Left);


if (item.CompareTo(tree.Data) > 0)

return Contains(ref tree.Right);
return true;




public void RemoveItem(T item)






Thank you in advance.

CompareTo: < 0 , > 0 or = 0

item > tree root

item < tree root

2 Answers
2

To check if a node is in the tree, you have a few options:

So your Contains method should look more like this:

Contains

public Boolean Contains(T item, ref Node<T> tree)

if (tree == null)

return false;


if (tree.data == item)

return true;



if (item.CompareTo(tree.Data) < 0)

return Contains(item, ref tree.Left);

if (item.CompareTo(tree.Data) > 0)

return Contains(item, ref tree.Right);




return false

public static bool Contains(Node root, int value)

if(root == null)
return false;
if(root.Value == value)
return true;
if(value < root.Value)
return Contains( root.Left,value);
else
return Contains( root.Right,value);



By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.