In this post, We will learn How to write a Java program to find the height or depth of a binary tree?
Logic is Very Simple:
The depth or height of a binary tree is the length of the longest path from the root to a leaf. The depth of a binary tree with no descendants is zero.
- If the tree is empty then the height of the tree is 0.
- else Start from the root and,
- Find the maximum depth of the left sub-tree recursively.
- Find the maximum depth of the right sub-tree recursively.
- The maximum depth of these two is (left and right subtree) height of the binary tree + 1.
For Example, the Height of this binary tree would be 3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/** * Function to find Height of Binary Tree * @param root * @return height of Tree */ public int findHeightOfBinaryTree(Node<Integer> root) { //if root is null if(root == null) return 0; /*Find the height or depth of left and right subtrees*/ int leftHeight = findHeightOfBinaryTree(root.left); int rightHeight = findHeightOfBinaryTree(root.right); //Remember Root Node height is zero return leftHeight > rightHeight ? leftHeight+1:rightHeight+1; } |
Time Complexity : O(n) , Space Complexity : O(n) for recusive Stack
Below is the Complete Source code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node of Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Function to find Height of Binary Tree * @param root * @return height of Tree */ public int findHeightOfBinaryTree(Node<Integer> root) { //if root is null if(root == null) return 0; /*Find the height or depth of left and right subtrees*/ int leftHeight = findHeightOfBinaryTree(root.left); int rightHeight = findHeightOfBinaryTree(root.right); //Remember Root Node height is zero return leftHeight > rightHeight ? leftHeight+1:rightHeight+1; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to find the height * or depth of a binary tree? * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Root Node Node<Integer> rootNode = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right of root Node rootNode.left = secondNode; rootNode.right = thirdNode; rootNode.left.left = fourthNode; rootNode.left.right = fifthNode; rootNode.right.left = sixthNode; rootNode.right.right = seventhNode; //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); int heightOfBinaryTree = binaryTree.findHeightOfBinaryTree(rootNode); System.out.println("Height of Binary Tree is:"+heightOfBinaryTree); } } |
The output of This Program:
Height of Binary Tree is:3
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Difference between binary and binary search trees
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
How do you find if two given binary trees are the same or identical
That’s all about Write a Java program to find the height or depth of a binary tree?
If you have any feedback or suggestion please feel free to drop in below comment box.