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.

Problem Link:

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

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.

Leave a Reply

Your email address will not be published.