CODEWITHSUNDEEP
c++recursiondata-structuresscopebinary-tree
Pranav Venkata
Pranav Venkata

Reputation: 59

recursive code for finding the height of a binary tree

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.

Upvotes: 0

Views: 365

Answers (2)

theWiseBro
theWiseBro

Reputation: 1529

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
}

Upvotes: 0

bipll
bipll

Reputation: 11940

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

Upvotes: 2

Related Questions