Your One-Stop Solution To Trees in C#

C#, a new widely-used programming language, was developed to meet the rising needs of new workloads and paradigm shifts in the programming community. When comparing a Tree to other data structures, like an array or a LinkedList, you don't have to state the tree's size, making it more efficient. Linked lists require large O(n) operations for insertion, deletion, and searching, while Trees do not.

You will cover the basics of trees in C# in this tutorial. Using the examples in this tutorial, you will learn how to implement trees in C#.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

What Are Trees in C#?

Data representation characterizes a hierarchical structure in the form of a tree. Every node in a tree comprises two distinct components (Data and References). The top node of the tree is referred to as the Root node, and the two products that fall beneath it are referred to as the "Left Subtree" and the "Right Subtree."

You can now go on to the next topic to learn about the types of trees now that you have a basic knowledge of the definition of Trees in C#.

What Are the Types of Trees in C#?

There are five types of Trees in C#:

• General Tree

When there is no restriction on the hierarchy of the tree, it is known as a general Tree. Children of a Node in the General Tree are unlimited; all other trees are subsets to this one.

• Binary Tree

A Binary tree is a type of tree where each parent can only have two children. The children are called left or right children and are one of the most utilized trees.

• Binary Search Tree

A binary search tree (BST) is a binary tree with some additional constraints. In BST, the value of the node's left child must be less than or equal to the value of its parent, while the value of the right child must be greater than or equal to the value of the parent.

• AVL Tree

An AVL Tree is an extension of a Binary search tree that can self-balance itself. Each node in an AVL tree is assigned a balancing factor used to determine whether a tree is balanced. A balance factor is a difference between the heights of the left subtree with the right subtree. In a perfect world, a balance factor can only be either 1, 0, or -1.

• Red-Black Tree

Another type of self-balancing tree is a red-black tree. In a red-black tree, each node has an extra bit. This extra bit is often considered the node's color (red or black). These colors are used to ensure that the tree stays balanced when new things are added and removed. Even though the balance of the tree isn't perfect, it's good enough to cut the time it takes to search and keep it around O(log n) time, where n is the number of elements in the tree.

So far, you have learned about the types of trees. Now you will explore the basic operations of trees in C#.

Learn the Ins & Outs of Software Development

Caltech Coding BootcampExplore Program

Some Basic Operations on Trees in C#

There are three basic operations you can perform on a Tree.

• Insertion

You can perform insertion on a tree in various ways. It depends on where you want to insert the new element.

• Deletion

When it comes to deleting a node, it can get tricky when you need to decide what to do with its left and right children.

• Search Operation

When searching for an element, you have to determine whether the current node matches the given value, or if you have to recur to the left and right sub-tree, repeating the same process.

Now, look at some of the terminologies related to Trees.

Some Terminology Related to Trees in C#

• Root Node: A root node is the first node from which the tree sprouts.
• Edge: An edge in a tree is the link that connects a parent and a child node.

• Parent Node: Any node with a child node attached to it is a parent node.
• Child Node: Any node with a parent node is a child node.
• Subtree: Each parent-child node pair makes a subtree of its own.

• Key: Every node is assigned a value in a tree structure, also called a key.
• Degree: Total number of children is the degree of that node.
• Sibling: All the nodes which share a parent are called sibling nodes.

• Height: The total number of edges that lie on the longest path from a leaf node to a node is the height of that node.
• Leaf Node: Any node which doesn't have any children is called a leaf node.
• Level: From top to bottom, each step is called a level.

Tree Traversal in Trees in C#

There are three types of tree traversal possible on Trees in C#

• Inorder

In this you will first visit the left subtree (node->left child->right child) root then root node then the right subtree (node->left child->right child).

• PreOrder

In this, you will first visit the root then the left subtree (node->left child->right child) then the right subtree (node->left child->right child).

• PostOrder

In this, you will first visit the left subtree (node->left child->right child), then the right subtree (node->left child->right child), then, at last, the root.

Now that you have looked at various operations and traversal on trees in C#. implement them in a code editor.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

Implementation of Trees in C#

You will be implementing the Trees in C# with the help of a code editor. 

Code: 

using System;

namespace C__Trees

{

    class Node

    {

        public Node LtNode { get; set; }

        public Node RtNode { get; set; }

        public int Data { get; set; }

    }

    class BinaryTree

    {

        public Node Root { get; set; }

        public bool Insert(int value)

        {

            Node before = null, after = this.Root;   

            while (after != null)

            {

                before = after;

//Is new node in left tree?

                if (value < after.Data) 

                    after = after.LtNode;

                 //Is new node in right tree?

 else if (value > after.Data)

 after = after.RtNode;

                else

                {

                    //Exist same value

                    return false;

                }

            }  

            Node newNode = new Node();

            newNode.Data = value;   

            if (this.Root == null)//Tree ise empty

                this.Root = newNode;

            else

            {

                if (value < before.Data)

                    before.LtNode = newNode;

                else

                    before.RtNode = newNode;

            }   

            return true;

        }   

        public Node Search(int value)

        {

            return this.Search(value, this.Root);            

        }  

        public void Delete(int value)

        {

            this.Root = Delete(this.Root, value);

        }  

        private Node Delete(Node parent, int key)

        {

            if (parent == null) return parent;   

            if (key < parent.Data) parent.LtNode = Delete(parent.LtNode, key); else if (key > parent.Data)

                parent.RtNode = Delete(parent.RtNode, key);   

            // if the value is the same as the parent's value, then this node is to be deleted  

            else

            {

                // the node with one or no child  

                if (parent.LtNode == null)

                    return parent.RtNode;

                else if (parent.RtNode == null)

                    return parent.LtNode;  

                // node with two children: Get the inorder successor (smallest in the right subtree)  

                parent.Data = MinValue(parent.RtNode);  

                // Delete the inorder successor  

                parent.RtNode = Delete(parent.RtNode, parent.Data);

            }  

            return parent;

        }

        private int MinValue(Node node)

        {

            int minv = node.Data;  

            while (node.LtNode != null)

            {

                minv = node.LtNode.Data;

                node = node.LtNode;

            } 

            return minv;

        } 

        private Node Search(int value, Node parent)

        {

            if (parent != null)

            {

                if (value == parent.Data) return parent;

                if (value < parent.Data)

                    return Search(value, parent.LtNode);

                else

                    return Search(value, parent.RtNode);

            }

            return null;

        }   

        public int GetDepth()

        {

            return this.GetDepth(this.Root);

        }   

        private int GetDepth(Node parent)

        {

            return parent == null ? 0 : Math.Max(GetDepth(parent.LtNode), GetDepth(parent.RtNode)) + 1;

        }

          public void PreOrder(Node parent)

        {

            if (parent != null)

            {

                Console.Write(parent.Data + " ");

                PreOrder(parent.LtNode);

                PreOrder(parent.RtNode);

            }

        }  

        public void InOrder(Node parent)

        {

            if (parent != null)

            {

                InOrder(parent.LtNode);

                Console.Write(parent.Data + " ");

                InOrder(parent.RtNode);

            }

        }  

        public void PostOrder(Node parent)

        {

            if (parent != null)

            {

                PostOrder(parent.LtNode);

                PostOrder(parent.RtNode);

                Console.Write(parent.Data + " ");

            }

        }

    }

    class Program

    {

        static void Main(string[] args)

        {

            BinaryTree binTree = new BinaryTree(); 

            binTree.Insert(11);

            binTree.Insert(21);

            binTree.Insert(78);

            binTree.Insert(31);

            binTree.Insert(101);

            binTree.Insert(51);

            binTree.Insert(82);         

            Node node = binTree.Search(51);

            int depth = binTree.GetDepth();           

            Console.WriteLine("PreOrder Traversal:");

            binTree.PreOrder(binTree.Root);

            Console.WriteLine();           

            Console.WriteLine("InOrder Traversal:");

            binTree.InOrder(binTree.Root);

            Console.WriteLine();           

            Console.WriteLine("PostOrder Traversal:");

            binTree.PostOrder(binTree.Root);

            Console.WriteLine();           

            binTree.Delete(78);

            binTree.Delete(82);           

            Console.WriteLine("After Remove Operation, Preorder Traversal:");

            binTree.PreOrder(binTree.Root);

            Console.WriteLine();           

            Console.ReadLine();

        }

    }

}

Applications of Trees in C#

• The XML Parser employs tree Algorithms.
• In machine learning, a decision-based algorithm is used based on trees.
• Tree data structures are also used in databases for indexing.
• Tree structures are also used by Domain name servers (DNS).
• File Explorer/mobile, computer, or any computer BST used in computer graphics.

By now, you have a good grip on the technical aspects of Trees in C#. 

Accelerate your career as a skilled MERN Stack Developer by enrolling in a unique Full Stack Developer - MERN Stack Master's program. Get complete development and testing knowledge on the latest technologies by opting for the MERN Stack Developer Course. Contact us TODAY!

Next Steps

The next lesson in your C# training can be "Graphs in C#." There are nodes and edges in a graph, which is a data structure that isn't straight. If you look at a graph, you can see lines or arcs that connect any two points in the graph. These points are called "nodes."

Gaining skills with trees in C# can greatly improve your coding abilities and provide you with new project opportunities. Thanks to this guide, you now have all the necessary knowledge to get started. Consider the Full Stack Developer - MERN Stack course if you want to increase your level of competence even more. It's the ideal approach to enhance your C# abilities with in-depth instruction on web programming.

The comments section below is open for questions and comments about this 'Trees in C#' tutorial. Happy learning!