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.

LeetCode Problem Link

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 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]

Leave a Reply

Your email address will not be published. Required fields are marked *