Calculating the Height of a Binary Search Tree in Data Structure
The quantity of edges connecting the root node and the farthest leaf node makes up the height of a binary search tree (BST). The deepest node in the tree's hierarchy can be thought of as its depth.
The height of a BST can be used to determine the complexity of certain algorithms that work with the tree, such as search and insertion. First, let's take a look at the general structure of a BST.
A BST consists of nodes, which are connected by edges. Each node has a value, and the right child of a node has a value that is greater than or equal to its parent node, while the left child of a node has a value that is less than or equal to the parent node.
Let's now examine how to determine a BST's height.
The height is calculated by calculating the number of edges from the root node to the farthest leaf node. The root node is at height 0, and each additional edge adds one to the height.
To calculate the height of a BST, start at the root node and traverse each branch until you reach a leaf node. You may determine the height of the BST by counting how many edges you have travelled along.
For example, consider the following BST:
6 4 8 2 5
The height of the BST can be calculated by counting the number of edges from the root node (6) to the furthest leaf node (2). In this case, the height is 2. In summary, calculating the height of a binary search tree is a simple process of counting the edges from the root node to the furthest leaf node. This can be used to determine the complexity of certain algorithms that work with the tree, such as search and insertion.
Implementation of the height of the Binary Search Tree in Java Language.
// Java program to calculate the height of a binary search tree
public class HeightBST
{
// A binary tree node
static class Node
{
int data;
Node left, right;
};
// Function to create a new Binary Tree node.
static Node newNode (int data)
{
// Allocate memory for new node
Node node = new Node ( );
// Assign data to the new node
node. data = data;
// Initialize left and right children as NULL.
node. left = null;
node. right = null;
return (node);
}
// Function to calculate the height of a binary search tree
static int height (Node root)
{
// Base case: Tree is empty
if (root == null)
return 0;
// If tree is not empty then height = 1 + max of left
//height and right heights
return (1+Math.max (height (root. left), height (root. right)));
}
// Driver program to test above functionalities
public static void main (String [ ] args)
{
// Create a Binary Tree having the following nodes.
// 1 // / \ // 2 3 // / \ // 4 5
Node root = newNode (10);
root. left = newNode (20);
root. right = newNode (30);
root. left. left = newNode (40);
root. left. right = newNode (50);
System. out. println (“ Height of the tree is “ + height (root));
}
}
Output:
Height of tree is 3
Perform a Depth-first search iteratively.
Return -1 if the tree is empty.
Otherwise, take the next action.
Call maxDepth(tree->left-subtree) to obtain the maximum depth of the left subtree.
Call maxDepth(tree->right-subtree) to obtain the maximum depth of the right subtree.
The maximum depths of the left and right subtrees for the current node are multiplied by 1.
max depth is equal to the sum of the maximum depths of the left and right subtrees plus one.
Give back max depth.
Implementation of the above algorithm using the java programming language.
// Finding the height of a tree using Java
// The structure for a Binary Tree Node.
class Node {
int data;
Node left, right;
Node (int item)
{
data = item;
left = right = null;
}
}
class BinaryTreeStructure {
Node root;
/* Find the number of nodes that make up the longest path from the root node to the farthest leaf node in a tree by computing its " maxDepth. " */
int maxDepthTree (Node node)
{
if (node == null)
return 0;
else {
/* calculate each subtree's depth. */
int leftDepth = maxDepthTree (node. left);
int rightDepth = maxDepthTree (node. right);
/* Utilize the greatest depth. */
if (leftDepth > rightDepth)
return (leftDepth + 1);
else
return (rightDepth + 1);
}
}
/* programme for testing the above features */
public static void main (String [ ] args)
{
BinaryTreeStructure t1 = new BinaryTreeStructure ( );
t1. root = new Node (10);
t1. root. left = new Node (20);
t1. root. right = new Node (30);
t1. root. left. left = new Node (40);
t1. root. left. right = new Node (50);
System. out. println (" Height of above created tree is "
+ t1. maxDepthTree (tree. root));
}
}
OUTPUT:
Height of the above generated tree is 3
Implementation of the above algorithm using the Python programming language.
# A Python 3 application to determine the depth of the largest tree
# Structure of the Binary Tree Node.
class Node :
# For creating a new node, a constructor is used.
def __init__ (self, data):
self. data = data
self. left = None
self. right = None
# Find the number of nodes that make up the longest path
# from the root node to the farthest leaf node in a tree
# by computing its " maxDepth. "
def maxDepthTree (node) :
if node is None :
return 0
else:
# calculate each subtree's depth.
leftDepth = maxDepthTree (node. left)
rightDepth = maxDepthTree (node. right)
# Utilize the larger height among the above generated two heights.
if (leftDepth > rightDepth):
return leftDepth+1
else:
return rightDepth+1
# Program for checking the above functionalites.
root = Node (10)
root. left = Node (20)
root. right = Node (30)
root. left. left = Node (40)
root. left. right = Node (50)
print (" Height of the tree which is generated above is %d "
% (maxDepthTree (root)))
OUTPUT:
Height of the above generated tree is 3
Implementation of the above algorithm using the C++ programming language.
// A C++ application to determine the depth of the largest tree
# include < bits / stdc ++ . h >
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
int data;
node* left;
node* right;
};
/* Find the number of nodes that make up the longest path from the root node to the farthest leaf node in a tree by computing its " maxDepth. ". */
int maxDepthTree (node* node)
{
if (node == NULL)
return 0;
else {
/* Get depth of all the sub trees. */
int leftDepth = maxDepthTree (node -> left);
int rightDepth = maxDepthTree (node -> right);
/* Among the generated two heights consider the largest one. */
if (leftDepth > rightDepth)
return (leftDepth + 1);
else
return (rightDepth + 1);
}
}
/* Allocating a new node with the supplied data and NULL left and right pointers is done using a helper function. */
node * newNodeCreation (int data)
{
node * Node = new node ( );
Node -> data = data;
Node -> left = NULL;
Node -> right = NULL;
return (Node);
}
// Program to check the above functions.
int main ( )
{
node * root = newNodeCreation (10);
root -> left = newNodeCreation (20);
root -> right = newNode (30);
root -> left -> left = newNodeCreation (40);
root -> left -> right = newNodeCreation (50);
cout << " Height of the above generated tree is " << maxDepthTree (root);
return 0;
}
Output:
Height of the above generated tree is 3
Another Algorithm for calculating the height of a Binary Tree.
Start from the root and move up the tree in level order.
Push null into the Q after initialising it with an empty queue, a configurable depth, and a push root.
While loop should be run till Q is not empty.
Q's front piece can be stored after being popped out.
If the queue is not empty, push NULL into the front of the queue if it is NULL, otherwise increase depth by one.
Otherwise, if the element is not NULL, check to see if it has any left or right children, and if not, put them into Q.
depth of return.