# Find Height of a Binary Search Tree

Height of a tree is the number of edges in longest path from root to a Leaf Node

Height of tree = Height of root

Height of tree with 1 node = 0

Depth of a node: Number of edges in path from root to that node

## Recursive Way to Find Height of a Binary Tree

``````#include<iostream>
using std::cout;
using std::endl;
using std::cin;

struct Node {
int data;
struct Node *left;
struct Node *right;
};

//Function to visit nodes in Inorder and print
void Inorder(Node *root) {
if(root == NULL)
{
return;
}
Inorder(root->left);          // Visit left subtree
cout << root->data << endl;  // Print data
Inorder(root->right);        // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,int data) {
// Return pointer which is a memory address

if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}

else if(data <= root->data)
{
root->left = Insert(root->left,data);
}
else
{
root->right = Insert(root->right,data);
}

return root;  // Return Root Address
}

/*
int FindHeight(Node* root)
{
if (root == NULL)
{
return -1; // Return Minus One because height of a leaf node is 0
}

int leftheight = FindHeight(root->left);
int rightheight = FindHeight(root->right);

return std::max(leftheight,rightheight) + 1;
}
*/

int FindHeight(Node* root)
{
if (root == NULL)
{
return -1;
}
return std::max(FindHeight(root->left), FindHeight(root->right)) + 1;
}

int main() {

Node* root = NULL;

root = Insert(root,15);
root = Insert(root,10);
root = Insert(root,20);
root = Insert(root,25);
root = Insert(root,17);

root = Insert(root,12);
root = Insert(root,8);
root = Insert(root,5);
root = Insert(root,2);

cout << "Inorder Traversal: " << endl;
Inorder(root);

int height;

height = FindHeight(root);

cout << "Height of Binary Tree: " << height << endl;
}
``````

Output:

``````Inorder Traversal:
2
5
8
10
12
15
17
20
25
Height of Binary Tree: 4
``````