CODEWITHSUNDEEP
c++c++11data-structures
Rohit
Rohit

Reputation: 101

Finding max height/depth in Binary Tree

After going through the basics of Binary Tree, I define it in C++ as below :

struct Node
{
    int key;
    Node *left;
    Node *right;
}*left=NULL,*right=NULL;

int getDepth(Node* t)
{
  if (t == NULL)
    return 0;
  else
    {
      int lDepth = getDepth(t->left);
      int rDepth = getDepth(t->right);

      if (lDepth > rDepth)
        return(lDepth + 1);
      else 
        return(rDepth + 1);
    }
}
int main()
{
    // root
    Node* root = new Node();
    root->key = 1;
    
    // left subtree
    root->left = new Node();
    root->left->key = 2;
    root->left->left = new Node();
    root->left->left->key = 4;
    root->left->right = new Node();
    root->left->right->key = 5;
    
    // right subtree
    root->right = new Node();
    root->right->key = 3;
}

Now If I try to find maximum height/depth using this code, it returns 3 instead of 2. What may be the reason? Also, Why I didn't find this way of assigning value to nodes anywhere?

Edit: Adding requested code

Upvotes: 1

Views: 236

Answers (1)

Bill Lynch
Bill Lynch

Reputation: 81916

Two issues:

1. You're incorrectly setting up the struct Node.

To define a type Node where the members have initial values, your syntax is slightly wrong. Instead, do:

struct Node {
    int key = 0;
    Node *left = nullptr;
    Node *right = nullptr;
};

2. The height of the tree is 3.

Here's a visual representation of the tree you've created. It has 3 levels.

         1
        / \
       2   3
      / \
     4   5

Upvotes: 4

Related Questions