# Tree Data Structure

## Introduction

Hi friends, today, I am going to discuss the small data structure topic of Trees. Before we go deep into this concept, I want to explain:
1. What is a Tree?
2. Why do we need a Tree?
3. Tree Terminologies

## What is a Tree?

• A Tree is used to represent data in a hierarchical format
• Every node in a tree has 2 components (Data and References)
• The top node of the tree is called the Root node and the 2 products under it are called "Left Subtree" and "Right Subtree".
Picture representation of a tree:

## Why do we need a Tree?

• When we compare a Tree with other data structures, like arrays or a LinkedList, we need not have to mention the size of the tree, hence it is space efficient.
• A linked list has big O(n) operation for insertion, deletion, and searching, whereas, with Trees, we do not have such a problem.

## Tree Terminologies

• "A"  represents the Root node (which do not have a parent)
• "Edge" is a link between Parent and a Chid (Ex: B to D)
• "Leaf" node with no children (Ex: D, E, F, G)
• "Sibling" children of the same parent (Ex: D and E are Siblings, they both have Same parent B)
• "Ancestor" parent, grandparent for a given node (Ex: D's ancestor is B and A)
• "Depth of a node" length of the path from the root to that node (Ex: D's depth is 2)
•  "Height of a Node" height from a particular node to the deepest node (leaf node) (Ex: height of B is 1 (B to D))

Binary Tree

A tree is said to be a Binary tree if each node has zero, one or two children.

Types of Binary Trees:
• Strict Binary Tree
• Full Binary Tree
• Complete Binary Tree
Strict BinaryTree

Each node has either two children or none.

Full Binary Tree

Each Non-leaf node has two children and all the leaf nodes are at the same level.

Complete Binary Tree

If all the levels are completely filled, except the last level and the last level has all the keys as left as possible

Tree Representation can be implemented in two ways.
1. Using a Linkedlist
2. Using an Array
In this article, I am going to implement a Linked list.

First, let's look at an example of how tree data is stored in a linked list. Below is the pictorial representation:

In the above image, the left image represents a Binary Tree and the Right Image represents a LinkedList arrangement of numbers. Inside the address of the root, the next node value is stored. When there is no leaf/ child node for a node then the memory address of that node will be represented as "null".

Create a blank Binary Tree:
1. public Class BinaryTreeByLinkedList{
2.
3.    BinaryNode root;
4.
5.   //Create a constructor
7.        this.root = null;
8.   }
9. }
Time Complexity: O(1)
Space Complexity: O(1)

## Depth - first Search of a Binary tree has 3 types

Pre-Order Traversal

Consider the above Binary tree as an example. In Pre-order traversal we need to traverse (Root, Left, Right). For the above example, the output should be 20,100,50,222,15,3,200,35

Algorithm for Pre-Order Traversal

Preorder(BinaryNode root)
if(root is null) return errorMessage
else
print root
Preorder(root.left)
Preorder(root.right)

Time Complexity: O(n)
Space Complexity: O(n)

Code for Pre Order Traversal:
1. // pre-order traversal of binary tree
2.                    void preOrder(BinaryNode node) {
3.                             if (node == null)
4.                                return;
5.                             Console.WriteLine(node.getValue() + " ");
6.                             preOrder(node.getLeft());
7.                             preOrder(node.getRight());
8.                          }//end of method
In-Order Traversal

Consider the above Binary tree as an example. With in-order traversal, we need to traverse (Left, Root, Right). In the above example, the output should be 222,50,100,15,20,200,3,35

Algorithm for In-Order Traversal

InOrderTraversal(BinaryNode root)
if(root equals null) return error message
else
InOrderTraversal(root.left)
print root
InOrderTraversal(root.right)
1. Code for In-Order Traversal
2.
3.               void inOrder(BinaryNode node) {
4.               if (node == null) {
5.               return;
6.               }
7.               inOrder(node.getLeft());
8.               Console.WriteLine(node.getValue() + " ");
9.               inOrder(node.getRight());
10.               }//end of method
Time Complexity: O(n)
Space Complexity: O(n)

Post-Order Traversal

Consider the above Binary tree as an example. For post-order traversal, we need to traverse (Left, Right, Root). For the above example, the output should be: 222, 50,100,15,20,200,3,35

Algorithm for Post-Order traversal

PostOrderTraversal(BinaryNode root)
if(root equals null) return errorMessage
else
PostOrderTraversal(root.left)
PostOrderTraversal(root.right)
print root

Time Complexity: O(n)
Space Complexity: O(n)
1. //Code for Post-Order traversal
2.
3. void postOrder(BinaryNode node) {
4.             if (node == null)
5.             return;
6.             postOrder(node.getLeft());
7.             postOrder(node.getRight());
8.             Console.WriteLine(node.getValue() + " ");
9.             }//end of method
10.
Level Order Traversal (Breadth-First Search of Binary Tree)

Consider above Binary Tree as an example. The output for above example is: 20,100,3,50,15,250,35,222

Algorithm for Level-Order traversal

LevelOrderTraversal(BinaryNode root)
CreateQueue(q)
enqueue(root)
while(q is notEmpty)
print root
enqueue()
dequeue() and Print

TimeComplexity: O(n)
SpaceComplexity: O(n)
1. Code for Level-Order Traversal
2.
3.         void levelOrder() {
4.                  // make a queue for level order. Queue is Interface and LinkedList is class
5.                  Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
7.                  while (!queue.isEmpty()) {
8.                              BinaryNode presentNode = queue.remove();
9.                              System.out.print(presentNode.getValue() + " ");
10.                              if (presentNode.getLeft() != null) {
12.                                    }
13.                              if (presentNode.getRight() != null){
15.                                    }
16.                           }
17.                   }// end of method

## Search a Value in Binary Tree

In order to search for a value in a Binary tree, it is always good to use a Queue rather than stack. (i.e Using level-Order traversal is the best way to search a value)

If we want to search the value "15" from above tree, we can use BFS. At Level3, we have the value 15.
1. // Search for a given value in binary tree
2.        void search(int value) {
3.                 Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
5.                 while (!queue.isEmpty()) {
6.                 BinaryNode presentNode = queue.remove();
7.                       if (presentNode.getValue() == value) {
8.                          Console.WriteLine("Value-"+value+" is found in Tree !");
9.                          return;
10.                        }else {
11.                             if (presentNode.getLeft()!=null)
13.                             if (presentNode.getRight()!=null)
15.                               }
16.                       }//end of loop
17.                 Console.WriteLine("Value-"+value+" is not found in Tree !");
18.              }//end of method

## Insertion of a Node in BinaryTree

Below are two conditions we need to consider while inserting a new value in BinaryTree:
1. When the Root is blank
2. Inserting a new node at the first vacant child
1. // inserts a new node at deepest place in Tree
2.                void insert(int value) {
3.                      BinaryNode node = new BinaryNode();
4.                      node.setValue(value);
5.                      if (root == null) {
6.                                  root = node;
7.                                  Console.WriteLine("Successfully inserted new node at Root !");
8.                                  return;
9.                      }
10.                      Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
12.                      while (!queue.isEmpty()) {
13.                                  BinaryNode presentNode = queue.remove();
14.                                  if (presentNode.getLeft() == null) {
15.                                              presentNode.setLeft(node);
16.                                              Console.WriteLine("Successfully inserted new node !");
17.                                               break;
18.                                  }else if (presentNode.getRight() == null) {
19.                                  presentNode.setRight(node);
20.                                  Console.WriteLine("Successfully inserted new node !");
21.                                  break;
22.                                  } else {
25.                                    }//end of else-if
26.                               }//end of loop
27.                           }//end of method

Delete Node in a Binary Tree

Two rules before deleting a node from a Binary Tree:
• When the value does not exist in a BinaryTree
• When the value needs to be deleted exists in the tree
If a value to be deleted exists in the tree, then we need to delete the deepest node from the BinaryTree. For example, if the node to be deleted is the root node, then find the deepest node in the binary tree and replace it with the root node, then delete the deepest node.

Code to delete the deepest node in the Binary Tree:
1. //Delete deepest node
2.            public void DeleteDeepestNode() {
3.                     Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
5.                     BinaryNode previousNode, presentNode = null;
6.                     while (!queue.isEmpty()) {
7.                                          previousNode = presentNode;
8.                                          presentNode = queue.remove();
9.                                          if (presentNode.getLeft() == null) {
10.                                                         previousNode.setRight(null);
11.                                                         return;
12.                                             }else if ((presentNode.getRight() == null)) {
13.                                                           presentNode.setLeft(null);
14.                                                            return;
15.                                             }
18.                                 }//end of while loop
19.                              }//end of method
20.         // get last node of last level of binary tree
21.                        public BinaryNode getDeepestNode() {
22.                                 // make an empty queue. Queue is Interface and LinkedList is class
23.                                 Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
25.                                 BinaryNode presentNode = null;
26.                                 while (!queue.isEmpty()) {
27.                                                   presentNode = queue.remove();
28.                                                   if (presentNode.getLeft() != null)
30.                                                   if (presentNode.getRight() != null)
32.                                                   }
33.                                 return presentNode;
34.                           }//end of method
35.
36.
37.            Code to Delete a value from BinaryTree
38.
39.               void deleteNodeOfBinaryTree(int value) {
40.                                   Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
42.                                    while (!queue.isEmpty()) {
43.                                             BinaryNode presentNode = queue.remove();
44.                                                // if node is found then copy deepest node here and delete deepest node.
45.                                             if (presentNode.getValue() == value) {
46.                                                            presentNode.setValue(getDeepestNode().getValue());
47.                                                            DeleteDeepestNode();
48.                                                            Console.WriteLine("Deleted the node !!");
49.                                                            return;
50.                                                }else {
51.                                             if (presentNode.getLeft() != null)
53.                                                            if (presentNode.getRight() != null)
55.                                          }
56.                              }//end of while loop
57.                                Console.WriteLine("Did not find the node!!");
58.                           }
Delete Entire BinaryTree
1. void deleteTree() {
2.     root = null;
3.     Console.WriteLine("Binary Tree has been deleted successfully");
4. }

## Conclusion

In this article, I have explained the types of trees, depth-first search, and breadth-first search. This article is completely for beginners. If there are any updates or anything needs attention, please feel free to comment below.