recursive code for finding the height of a binary tree

Question

I am trying to find the height of a binary tree and here is my attempt at the same

#include<iostream>
#include<stack>
using namespace std;
int total = 0;
int length = -1;
class Node{
    public:
        int data;
        Node *left;
        Node *right;
        Node(int k){
            data = k;
            left = right = NULL;
        }
};
void height(Node *root){
    if(root==NULL)
        return;
    length++;
    if(length>total)
        total = length;
    height(root->left);
    height(root->right);
}
int main(){
    Node *root = new Node(3);
    root->left = new Node(4);
    root->left->left = new Node(5);
    root->right = new Node(6);
    root->right->left = new Node(7);
    height(root);
    cout<<total;
    return 0;
}

here length and total have been declared as global variables having values -1 and 0 respectively. When I run the code, the output which I am getting is the number of nodes in the tree - 1 but not the height of the tree. Please let me know my mistake here.

@theWiseBro I have included working code for the same. Please look into the issue — Pranav Venkata
– Pranav Venkata, Commented Mar 22, 2020 at 12:26

bipll · Accepted Answer · 2020-03-22 12:22:26Z

2

Sure, you're incrementing length on every node.

If you're doing it recursively, it is actually very simple:

std::size_t height(Node const *root) {
    if(!root) return 0;
    return 1 + std::max(height(root->left), height(root->right));
}

answered Mar 22, 2020 at 12:22

bipll

12k1 gold badge21 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

theWiseBro · Accepted Answer · 2020-03-22 12:29:21Z

0

Your approach is more of a backtracking than a simple recursion. In this approach you should be mindful to revert back to the original state at each step. Here length is always being incremented. You should revert it back.

void height(Node *root){
    if(root==NULL)
        return;
    length++;
    total = std::max(total,length+1); // Either this or initialize length as 0
    height(root->left);
    height(root->right);
    length--; // <--- Add this line
}

edited Mar 22, 2020 at 12:29

answered Mar 22, 2020 at 12:21

theWiseBro

1,53913 silver badges11 bronze badges

Collectives™ on Stack Overflow

recursive code for finding the height of a binary tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related