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

Binary Search Tree Implementation in C#

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 search tree code in c#

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