This tutorial explains the Height of the Binary Tree with some examples. In the following example there is a B Tree given, We have to find the Height of The Tree.
What is the Height of The Binary Tree?
The Height of a Tree Is equal to the largest numbers of edges from the Root to the most distant leaf node. In other words, it is the Height of the Root Node in the whole Binary Tree.
How to Calculate the Height of Tree?
Recursively calculate the height of left and right subtree and of a node and assign height to the node as max to the heights of two children plus 1. See below code.
NOTE : Height of the empty Tree is 0(zero).
Example
Explanation:
1. Create a Binary Tree.
2. Implement a base condition of root null.
3. To get the height of Tree, get the total height of left subtree.
4. Get the total height of right subtree.
5. Compare both height and the final height will be the maximum height of the Tree.
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary tree
static class BinaryTree {
static int id = -1;
public static Node createBinary(int nodes[]) {
id++;
if (nodes[id] == -1) {
return null;
}
Node myNode = new Node(nodes[id]);
myNode.left = createBinary(nodes);
myNode.right = createBinary(nodes);
return myNode;
}
}
// height of the tree
public static int heightOfTree(Node root) {
if (root == null) {
return 0;
}
int leftHeight = heightOfTree(root.left);
int rightHeight = heightOfTree(root.right);
int maxHeight = Math.max(leftHeight, rightHeight) + 1;
return maxHeight;
}
public static void main(String[] args) {
int nodeArr[] = { 1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1 };
BinaryTree tree = new BinaryTree();
Node result = tree.createBinary(nodeArr);
int height = heightOfTree(result);
System.out.println(height);
}
}
Answer: 3
Time Complexity : O(N) See Tree Traversal.
Auxiliary Space : O(N) due to Recursive Stack
Conclusion: We got the height of the given tree successfully.
Thank you for reaching out this tutorial, for any doubt and issue you can comment in the comments section below. You can also post your content here. Learn more about it from Here.
