# How to find the maximum height of a Binary tree – LeetCode Solution [Easy]

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.

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Height of an empty Binary tree is -1. And as you can see, height of above tree 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

//
//  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;
}



Here’s a working example:

https://ideone.com/egPHHv

For LeetCode problem, return 0 for an empty tree to get AC.