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   
  6.   public BinaryTreeByLinkedList(){  
  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>();  
  6.                  queue.add(root);  
  7.                  while (!queue.isEmpty()) {  
  8.                              BinaryNode presentNode = queue.remove();  
  9.                              System.out.print(presentNode.getValue() + " ");  
  10.                              if (presentNode.getLeft() != null) {  
  11.                                       queue.add(presentNode.getLeft());  
  12.                                    }  
  13.                              if (presentNode.getRight() != null){  
  14.                                       queue.add(presentNode.getRight());  
  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>();  
  4.                 queue.add(root);  
  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)  
  12.                                   queue.add(presentNode.getLeft());  
  13.                             if (presentNode.getRight()!=null)  
  14.                                   queue.add(presentNode.getRight());  
  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>();  
  11.                      queue.add(root);  
  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 {  
  23.                                     queue.add(presentNode.getLeft());  
  24.                                     queue.add(presentNode.getRight());  
  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>();  
  4.                     queue.add(root);  
  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.                                             }  
  16.                                             queue.add(presentNode.getLeft());  
  17.                                              queue.add(presentNode.getRight());  
  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>();  
  24.                                 queue.add(root);  
  25.                                 BinaryNode presentNode = null;  
  26.                                 while (!queue.isEmpty()) {  
  27.                                                   presentNode = queue.remove();  
  28.                                                   if (presentNode.getLeft() != null)  
  29.                                                         queue.add(presentNode.getLeft());  
  30.                                                   if (presentNode.getRight() != null)  
  31.                                                          queue.add(presentNode.getRight());  
  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>();  
  41.                                    queue.add(root);  
  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)  
  52.                                                            queue.add(presentNode.getLeft());  
  53.                                                            if (presentNode.getRight() != null)  
  54.                                                                      queue.add(presentNode.getRight());  
  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.