C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

Home » Data Structure

Learn: How to find the height or maximum depth of a binary search tree? This article includes definition, algorithm and implementation in C++ program. Submitted by Abhishek Jain, on July 30, 2017

The Height (or depth) of a tree is defined to be the maximum level of any node in the tree. Some authors define depth of a node to be the length of the longest path from the root node to that node, which yields the relation:

Depth of the tree = Height of the tree - 1

Reference: http://codersmaze.com/data-structure-explanations/trees-in-data-structure/

Algorithm:

FindHeight( Node root) If root=NULL return 0 Else int l=FindHeight (root->left) int r=FindHeight(root->right) Return max(l,r)+1 [End If] [End]

Consider the program:

#include<iostream> using namespace std; struct node { int data; node* left; node* right; }; struct node* getNode(int data) { node* newNode=new node(); newNode->data=data; newNode->left=NULL; newNode->right=NULL; return newNode; } void inorder(struct node* root) { if (root != NULL) { inorder(root->left); cout<<root->data<<" "; inorder(root->right); } } struct node* Insert(struct node* root, int data) { if (root == NULL) return getNode(data); if (data < root->data) root->left = Insert(root->left, data); else if (data > root->data) root->right = Insert(root->right, data); return root; } int main() { node* root=NULL; root=Insert(root,20); Insert(root,15); Insert(root,25); Insert(root,18); Insert(root,10); Insert(root,16); Insert(root,19); cout<<"Before Insertion: "; cout<<"\nInorder: "; inorder(root); cout<<endl; root=Insert(root,17); cout<<"\nNode Inserted"<<endl; cout<<"\nAfter Insertion: "; cout<<"\nInorder: "; inorder(root); cout<<endl; return 0; }

Output

Inorder: 14579 Height of the tree is 3 Max. Depth of the tree is 2

Liked this article? Do share with your friends :)

C, C++, Java, D.S., Python, .Net, SQL, PL/SQL, Ajax, PHP, JavaScript, CSS, HTML, C programs, C++ programs, Java programs, C# programs, DS programs, C aptitude, C++ aptitude, Java aptitude, DBMS aptitude, O.S., Networking, Embedded systems, Nanotechnologies, Linux, DOS, puzzles, syntaxes,