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.

What is a Tree?
Why do we need a Tree?
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.

Tree

Why do we need a Tree?

When we compare a Tree with other data structures, like arrays or a LinkedList, we need not mention the size of the tree, hence it is space efficient.
A linked list has a 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 does not have a parent).
"Edge" is a link between a Parent and a child (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.

Strict BinaryTree

Full Binary Tree

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

Binary Tree

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.

Complete Binary

Tree Representation can be implemented in two ways.

Using a LinkedList
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.

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)

A 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;
    System.out.println(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

void inOrderTraversal(BinaryNode root) {
    if (root == null) {
        System.out.println("Error: Null root");
        return;
    } else {
        inOrderTraversal(root.left);
        System.out.println(root);
        inOrderTraversal(root.right);
    }
}

// Code for In-Order Traversal

void inOrder(BinaryNode node) {
    if (node == null) {
        return;
    }
    inOrder(node.getLeft());
    System.out.println(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.

void postOrderTraversal(BinaryNode root) {
    if (root == null) {
        return errorMessage;
    } else {
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(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());
    System.out.println(node.getValue() + " ");
} // end of method

Level Order traversal (Breadth-first search of Binary tree)

Consider the above Binary Tree as an example. The output for the 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

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

// Code for Level-Order Traversal

void levelOrder() {
    // Make a queue for level order. Queue is an interface and LinkedList is a 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 the Binary tree

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

Value in Binary

If we want to search for the value "15" from the above tree, we can use BFS. At Level 3, 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) {
            System.out.println("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
    System.out.println("Value-" + value + " is not found in Tree!");
} // end of method

Below are two conditions we need to consider while inserting a new value in BinaryTree.

When the Root is blank
Inserting a new node at the first vacant child.

// Inserts a new node at the deepest place in the tree
void insert(int value) {
    BinaryNode node = new BinaryNode();
    node.setValue(value);
    if (root == null) {
        root = node;
        System.out.println("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);
            System.out.println("Successfully inserted new node!");
            break;
        } else if (presentNode.getRight() == null) {
            presentNode.setRight(node);
            System.out.println("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();
            System.out.println("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
    System.out.println("Did not find the node!!");
}

Delete entire Binary tree

void deleteTree() {
    root = null;
    System.out.println("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 that needs attention, please feel free to comment below.

3 Comments

Join the conversation! Your thoughts help the community grow.

Dheeraj S Pawar2y ago
In tree terminologies section, almost all the example given are wrong, check it once again.
Elvis Chimuse2y ago
Where you said d and e have the same parent, can you please explain. is it not e and f.
Lija Jose5y ago
Wonderful Article, a suggestion would be not to use Linked List or Array that would give space complexity of O(1) and instead create a BinaryTree class containing BinaryNode property with insert delete functions.