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

## Introduction to Tree

Tree program in C data structuredata 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 C Implementation

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.

### Implementation of Binary Search Tree in C Programming (BsT)

 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();` `        ``}` `    ``}` `}`