Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Height of an empty Binary tree is -1. And height of the above tree, as you can see is 2.
Pseudocode
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
1. Base case: return -1, if root is NULL. 2. Get the maximum height of left subtree (recursively). 3. Get the maximum height of right subtree (recursively). 4. Return the max of (left-subtree height + 1, right-subtree height + 1).
We advise you to implement the code for this problem before reading the C++ implementation below.
Code Implementation
//
// main.cpp
// Height of Binary Tree
//
// Created by Himanshu on 11/09/21.
//
#include <iostream>
#include <queue>
using namespace std;
struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int maxHeight (Node *root) {
if (!root) {
return -1;
}
int leftHt = maxHeight(root->left);
int rightHt = maxHeight(root->right);
if (leftHt > rightHt) {
return (leftHt + 1);
} else {
return (rightHt + 1);
}
}
int main() {
Node *root = newNode(1);
root->left = newNode(20);
root->right = newNode(21);
root->right->left = newNode(30);
root->right->right = newNode(31);
cout<<"The height of given tree is: "<<maxHeight(root)<<endl;
return 0;
}
Output
The height of given tree is: 2
Here’s a working example: Solution
For LeetCode problem, return 0 for an empty tree to get AC.
One thought on “How to find the maximum height of a Binary tree – LeetCode Solution [Easy]”