How to find a height of a tree data structure in Java

Introduction

The Tree is a non linear data structure consisting of nodes and edges. Depending upon the type of tree, it can have 0 or more child nodes. For example, Each node in a binary tree can have 0, 1 or 2 child nodes. Whereas, the B+ tree of order 5 can have 4 data values in each node and maximum 5 child nodes attached to a node.

Here, we will first construct a binary search tree in Java. Thereafter, we will write a java code to find the height of the binary tree. The height of a node is the length of the longest downward path from a root node till the leaf node. The height of the root is the height of the tree. Now, in order to calculate the height of the tree, we have to traverse through each node of the tree in order to get all permutations and combinations.

Advertisement

There are two ways to calculate the height of a tree.

  • Recursive Approach
  • Iterative Way

 

Constructing a Binary Search Tree

In order to construct a binary search tree, we need to make sure that none of the properties of binary search tree is violated while inserting a node.
Here, the each call to the insertion method will insert one node to a binary search tree. The first call to insertion will make that node as a root node. All the other insertions will take place considering the value of root node. Here, we will construct the binary search tree as shown in the figure below.
Height of a tree
The code below shows the insertion function which places the node in a tree such that none of the properties of binary search tree is violated.

// Creating a node class
class Node {
    Node left;
    Node right;
    int data;
    // Initializing to null
    Node() {
        left = null;
        right = null;
        data = -1;
    }
}
// Inserting a node in Binary search tree
public class Main {
    public static void main(String[] args) {
        // Creating a root node
        Node root = new Node();

        Main m = new Main();

        // Calling insertion function to insert some nodes
        m.insertion(root, 10);
        m.insertion(root, 5);
        m.insertion(root, 20);
        m.insertion(root, 30);
        m.insertion(root, 25);
        m.insertion(root, 2);
    }

    void insertion(Node root, int val) {
        // Condition if this is a first node then it will be considered as a root
        if (root.data == -1) {
            System.out.println(val + " Inserted as root");
            root.data = val;
            // Else part will be executed for all the other insertions
        } else {
            // Pointer to move around tree to search for a place of new node
            Node p = root;
            // Creating a new node and writing a value in the data part
            Node n = new Node();
            n.data = val;
            // Iterating to search for an appropriate place of new node
            while (true) {
                // if val is less than the current node p indicates that new node will be inserted on left subtree
                if (val < p.data) {
                    if (p.left == null) {
                        System.out.println(val + " Inserted on left of " + p.data);
                        p.left = n;
                        break;
                    } else {
                        p = p.left;

                    }
                }
                // if val is greater than the current node p indicates that new node will be inserted on right subtree
                else {
                    if (p.right == null) {
                        System.out.println(val + " Inserted on right of" + p.data);
                        p.right = n;
                        break;
                    } else {
                        p = p.right;
                    }
                }
            }
        }
    }
}

Output

10 Inserted as root
5 Inserted on left of 10
20 Inserted on right of10
30 Inserted on right of20
25 Inserted on left of 30
2 Inserted on left of 5

 

Different ways to finding the height of a tree

Method-1: Recursive Approach to find the Height of a Tree

When we want to find the height of a tree. Firstly, we will need to calculate the height of it’s left subtree and right subtree recursively. Now, each of these subtrees may have a left and right subtree attached, hence recursion would apply until the subtrees are null. Finally, we will compare the heights of the left and right subtree and return the maximum of two. Thereafter, we will add 1 to them as that is the height between the topmost node and its children to obtain the correct height of a tree.

 

Note that we will add the height function to the code we have written to construct binary search tree and call it from the main function. Here, for the tree shown above we will get the height of tree  as 3.

    int height(Node root) {
        // Return if reached null node or last level
        if (root == null)
            return -1;

        // Traversing left subtree
        int heightleftsubtree = height(root.left);

        // Traversing right subtree
        int heightrightsubtree = height(root.right);

        // return the height which is maximum of left or right sub tree after adding 1
        return Math.max(heightleftsubtree, heightrightsubtree) + 1;
    }

 

Method-2: Iterative Approach to find the Height of a Tree

In this approach, to find the height of a tree we will calculate the number of levels in tree. So, we will use Queue to store the child nodes while traversing across the tree. We will create a queue and add root to it along with the child nodes of the root. Thereafter, we traverse along the tree and pop the node from the queue and traverse on tree. For each iteration we will pop the latest element added to the queue and add the elements of the next level to the queue. We will perform this until the queue size becomes zero. Here, we will add 1 for each traversed level.

Advertisement

Note that we will add the height function to the code we have written to construct binary search tree and call it from the main function. Here, for the tree shown above we will get the height of tree  as 3.

int height1(Node root) {
    // Return if reached null node or last level
    if (root == null)
        return -1;
    // Creating an empty queue 
    Queue queue = new LinkedList < > ();
    // Adding root to the queue and initialize the height
    queue.add(root);
    int height = -1;

    // Traverse a tree till queue is empty
    while (!queue.isEmpty()) {
        int size = queue.size();
        height++;
        while (size > 0) {
            Node Node = queue.remove();
            if (Node.left != null)
                queue.add(Node.left);

            if (Node.right != null)
                queue.add(Node.right);
            size--;
        }
    }
    // return the height to the main function
    return height;
}

 

Summary

The knowledge of obtaining the height of the tree is very useful while working on real time applications. In many situations, we will need to get the height of a tree. For example, while constructing an AVL tree, we will need to get the height of tree multiple times. In this tutorial, we covered creation, insertion and finding the height of a tree using both iterative and recursive approach with java code. As per the requirement of an application, we can choose an appropriate approach to find the height of a tree. We learned in detail about this with an example.

All in all, this tutorial, covers everything that you need to know in order to have a clear view on finding height of a tree using Java.

 

References

Classes in Java

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment

X