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.
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.
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.
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
