Major property of the binary search tree is self-similarity (every leaf can be root for another smaller binary search tree). For that reason, in BST we can use recursive functions to find or count the data. Searching through BST is very efficient, since all of the data are indexed. Binary search tree implementation in C# is subject of this article. First thing we need to implement binary search tree is to define node class.

public class *node_in_sbt *

{

public int data_value;

public *node_in_sbt* left, right;

public ** node_in_sbt**(int a)

{

* this*.data_value = a;

left = null;

right = null;

}

}

Next class we need to have is class for binary search tree.

public class Tree

{

public node_in_sbt root_of_the_tree;

public *Tree()*

{

root_of_the_tree = null;

}

Apart from constructor *Tree()* with no parameters, we can use polymorphism and add another constructor that takes array as input parameter. Code that insert node in binary search tree is following:

public Tree(int[] input)

{

root_of_the_tree = null;

for (int i = 0; i < input.Length; i++)

{

**this**.insert(**this**.root_of_the_tree, **this**.**addNode**(input[i]));

}

}

Method insert used in the constructor with an array as input parameter must have two parameters:

- node that is root of the tree
- integer number that will be added by another method called addNode that has return value with type of an node of the tree, and takes int as input parameter.

public node_in_sbt addNode(int int_data)

{

node_in_sbt temp = new node_in_sbt(int_data);

if (root_of_the_tree == null) root_of_the_tree = temp;

return temp;

}

addNode simply create and return node back to the tree. If there was no root of the tree this node becomes the root. Otherwise, method insert will do the right positioning.

public void insert(node_in_sbt root, node_in_sbt newNode)

{

while (root != null)

{

if (newNode.data_value > root.data_value)

{

if (root.right == null)

{

root.right = newNode;

MessageBox.Show(root.right.data_value.ToString(), “Right”);

break;

}

root = root.right;

MessageBox.Show(root.data_value.ToString(), “new root Right”);

}

else

{

if (root.left == null)

{

root.left = newNode;

MessageBox.Show(newNode.data_value.ToString(), “Left”);

break;

}

root = root.left;

MessageBox.Show(root.data_value.ToString(), “new root Left”);

}

}

}

So method insert takes two parameters (both of the node type) and returns nothing, since it is member of the tree class. Another method would be useful for presenting ordered data (showing values from the left, then root, then right, then next root and so forth. This method must be called recursively (when called).

public void **ordered**(node_in_sbt root)

{

string str_return = “”;

if (root != null)

{

**ordered**(root.left);

str_return += root.data_value.ToString() + ” “;

MessageBox.Show(str_return);

**ordered**(root.right);

}

}

With this code, we can now implement binary search tree in C#, on following array

int[] input = { 53, 72, 14, 7, 17, 12, 1};

Tree **bst** = new Tree(input);

**bst**.ordered(**bst**.root_of_the_tree);

**External links:**

Binary Search Tree Implementation on bluesharktutorials

Binary Search Tree Implementation on codereview.stackexchange.com

Binary Search Tree Implementation on vcskicks

Binary Search Tree Implementation on c-sharpcorner.com

Binary Search Tree Implementation on introprogramming

Binary Search Tree Implementation on stackoverflow.com

## Leave a Reply