# Binary Search Tree Implementation in C# | Data Structure Using C#

### Introduction to Tree

Tree is a data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as set of linked nodes. A tree can also be seen as collection of nodes, where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

A tree exhibits following properties:
•  There is exactly one root
•  All nodes except the root have precisely one parent.
•  There are no cycles.

### Binary Tree

The simplest form of a tree is a binary tree, one in which all nodes have at most two children. For a given node in a binary tree, the first child is referred to as the left child, while the second child is referred to as the right child.

Terminology
Parent Node: A node that has a child is called the child’s parent node.
Root Node: Special node of the tree having no parent.
Siblings: Any pair of node having same parent node.
Ancestor: The predecessor of a node together with all the ancestors of the predecessor of a node. The root node has no ancestors.
Descendant: The children of a node together with all the descendants of the children of a node. A leaf node has no descendants.

### Binary Search tree

Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
The height of a binary (search) tree equals the number of nodes from the root node to the deepest node of the tree.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DataStructure {     class BST     {         // Creating Binary Search Tree node class         class Node         {             public int data;             public Node left;             public Node right;             public Node(int value)             {                 this.data = value;                 left = null;                 right = null;             }         }         class BinarySearchTree         {             public Node root;             static int count;             public BinarySearchTree()             {                 root = null;             }             // Creates and returns a BST node             public Node addNode(int data)             {                 Node temp = new Node(data);                 if (root == null)                     root = temp;                 count++;                 return temp;             }             // Procedure inserts 'newNode' in BST at proper position             public void insert(Node root, Node newNode)             {                 while (root != null)                 {                     if (newNode.data > root.data)                     {                         if (root.right == null)                         {                             root.right = newNode;                             break;                         }                         root = root.right;                     }                     else                     {                         if (root.left == null)                         {                             root.left = newNode;                             break;                         }                          root = root.left;                     }                 }             }             // Recursive Procedure travels BST tree in Inorder Fashion (left subtree -> root -> right Subtree)             public void inorder(Node root)             {                 if (root!=null)                 {                     inorder(root.left);                     Console.Write(root.data + " ");                     inorder(root.right);                 }             }         }         static void Main(string[] args)         {             BinarySearchTree bst = new BinarySearchTree();             // Inserting Nodes to Binary search Tree             bst.insert(bst.root, bst.addNode(21));             bst.insert(bst.root, bst.addNode(19));             bst.insert(bst.root, bst.addNode(7));             bst.insert(bst.root, bst.addNode(19));             bst.insert(bst.root, bst.addNode(16));             bst.insert(bst.root, bst.addNode(13));             bst.insert(bst.root, bst.addNode(8));             bst.insert(bst.root, bst.addNode(22));             // Traversing BST in Inorder fashion             bst.inorder(bst.root);             Console.ReadKey();         }     } }