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:

public Class BinaryTreeByLinkedList{

   BinaryNode root;

  //Create a constructor
  public BinaryTreeByLinkedList(){
       this.root = null;
  }
}

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:

// pre-order traversal of binary tree
                   void preOrder(BinaryNode node) {
                            if (node == null)
                               return;
                            Console.WriteLine(node.getValue() + " ");
                            preOrder(node.getLeft());
                            preOrder(node.getRight());
                         }//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)

Code for In-Order Traversal

              void inOrder(BinaryNode node) {
              if (node == null) {
              return;
              }
              inOrder(node.getLeft());
              Console.WriteLine(node.getValue() + " ");
              inOrder(node.getRight());
              }//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)            

//Code for Post-Order traversal

void postOrder(BinaryNode node) {
            if (node == null)
            return;
            postOrder(node.getLeft());
            postOrder(node.getRight());
            Console.WriteLine(node.getValue() + " ");
            }//end of method

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)   

Code for Level-Order Traversal

        void levelOrder() {
                 // make a queue for level order. Queue is Interface and LinkedList is class
                 Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                 queue.add(root);
                 while (!queue.isEmpty()) {
                             BinaryNode presentNode = queue.remove();
                             System.out.print(presentNode.getValue() + " ");
                             if (presentNode.getLeft() != null) {
                                      queue.add(presentNode.getLeft());
                                   }
                             if (presentNode.getRight() != null){
                                      queue.add(presentNode.getRight());
                                   }
                          }
                  }// 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. 

// Search for a given value in binary tree
       void search(int value) {
                Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                queue.add(root);
                while (!queue.isEmpty()) {
                BinaryNode presentNode = queue.remove();
                      if (presentNode.getValue() == value) {
                         Console.WriteLine("Value-"+value+" is found in Tree !");
                         return;
                       }else {
                            if (presentNode.getLeft()!=null)
                                  queue.add(presentNode.getLeft());
                            if (presentNode.getRight()!=null)
                                  queue.add(presentNode.getRight());
                              }
                      }//end of loop
                Console.WriteLine("Value-"+value+" is not found in Tree !");
             }//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        

// inserts a new node at deepest place in Tree
               void insert(int value) {
                     BinaryNode node = new BinaryNode();
                     node.setValue(value);
                     if (root == null) {
                                 root = node;
                                 Console.WriteLine("Successfully inserted new node at Root !");
                                 return;
                     }
                     Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                     queue.add(root);
                     while (!queue.isEmpty()) {
                                 BinaryNode presentNode = queue.remove();
                                 if (presentNode.getLeft() == null) {
                                             presentNode.setLeft(node);
                                             Console.WriteLine("Successfully inserted new node !");
                                              break;
                                 }else if (presentNode.getRight() == null) {
                                 presentNode.setRight(node);
                                 Console.WriteLine("Successfully inserted new node !");
                                 break;
                                 } else {
                                    queue.add(presentNode.getLeft());
                                    queue.add(presentNode.getRight());
                                   }//end of else-if
                              }//end of loop
                          }//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:

//Delete deepest node
           public void DeleteDeepestNode() {
                    Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                    queue.add(root);
                    BinaryNode previousNode, presentNode = null;
                    while (!queue.isEmpty()) {
                                         previousNode = presentNode;
                                         presentNode = queue.remove();
                                         if (presentNode.getLeft() == null) {
                                                        previousNode.setRight(null);
                                                        return;
                                            }else if ((presentNode.getRight() == null)) {
                                                          presentNode.setLeft(null);
                                                           return;
                                            }
                                            queue.add(presentNode.getLeft());
                                             queue.add(presentNode.getRight());
                                }//end of while loop
                             }//end of method
        // get last node of last level of binary tree
                       public BinaryNode getDeepestNode() {
                                // make an empty queue. Queue is Interface and LinkedList is class
                                Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                                queue.add(root);
                                BinaryNode presentNode = null;
                                while (!queue.isEmpty()) {
                                                  presentNode = queue.remove();
                                                  if (presentNode.getLeft() != null)
                                                        queue.add(presentNode.getLeft());
                                                  if (presentNode.getRight() != null)
                                                         queue.add(presentNode.getRight());
                                                  }
                                return presentNode;
                          }//end of method


           Code to Delete a value from BinaryTree

              void deleteNodeOfBinaryTree(int value) {
                                  Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
                                   queue.add(root);
                                   while (!queue.isEmpty()) {
                                            BinaryNode presentNode = queue.remove();
                                               // if node is found then copy deepest node here and delete deepest node.
                                            if (presentNode.getValue() == value) {
                                                           presentNode.setValue(getDeepestNode().getValue());
                                                           DeleteDeepestNode();
                                                           Console.WriteLine("Deleted the node !!");
                                                           return;
                                               }else {
                                            if (presentNode.getLeft() != null)
                                                           queue.add(presentNode.getLeft());
                                                           if (presentNode.getRight() != null)
                                                                     queue.add(presentNode.getRight());
                                         }
                             }//end of while loop
                               Console.WriteLine("Did not find the node!!");
                          }

Delete Entire BinaryTree               

void deleteTree() {
    root = null;
    Console.WriteLine("Binary Tree has been deleted successfully");
}

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.