The height of a binary tree is found using the recursive Depth-First Search (DFS) algorithm, as shown below:
Base case: If there is no node, return 0.
Else: If there are 1 or 2 children, return the maximum of the height of the left and right sub-trees, plus 1 to account for the current node. The height of a sub-tree is found by recursively calling the function, and passing the child node as the parameter.
#include <iostream> using namespace std; struct Node{ Node* left; Node* right; }; Node* createTree(){ Node* root = new Node(); // Creating 2nd level: Node* one = new Node(); Node* two = new Node(); root->left = one; root->right = two; // Creating 3rd level: Node* three = new Node(); Node* four = new Node(); Node* five = new Node(); one->left = three; two->left = four; two->right = five; return root; } int findMax(int a, int b){ if(a >= b) return a; else return b; } int findHeight(Node* root){ // Base case: if(root == NULL) return 0; return findMax(findHeight(root->left), findHeight(root->right)) + 1; } int main() { Node* root = createTree(); cout << "Height of tree: " << findHeight(root); return 0; }
RELATED TAGS
View all Courses