Finding max height/depth in Binary Tree

Question

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

Hard to tell if you don't show your algorithm for finding the depth - but I'm guessing you're counting the root node. — Timon van der Berg
– Timon van der Berg, Commented May 20, 2021 at 14:26
1. You missed to add the code for calculating depth. 2. You missed to initialise child node pointers. struct Node { /*... */ } *left = NULL, *right = NULL; creates two global variables of type Node*. If you want to provide default values must look like this: struct Node { Node* left = nullptr; Node* right = nullptr; }; (side note: nullptr is a C++ keyword you should prefer over old/obsolete C macros (NULL). — Aconcagua
– Aconcagua, Commented May 20, 2021 at 14:27

Bill Lynch · Accepted Answer · 2021-05-20 14:41:50Z

4

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.

answered May 20, 2021 at 14:41

Bill Lynch

82.4k16 gold badges132 silver badges181 bronze badges

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

4 Comments

Rohit Over a year ago

But here, height is 2

al3c Over a year ago

Depends how you count, that page says "Height of empty tree is 0", however your code has 0 for the "null" tree, 1 for a tree with just a root etc... You should change the null case in getDepth to return -1

Aconcagua Over a year ago

@Rohit The link you provided is wrong. It says height is 2, but actually it is 3, there, too. The code provide there would calculate height as 3 as well. Additionally, once more an example of bad code on geeks for geeks (including bits/stdc++.h, using namespace std, inconsistent indentation style, else after return, ...).

Wyck Over a year ago

That geeks for geeks article is absolutely terrible. Defining the height of an empty tree (with no nodes) to be 0 and defining the height of a tree with 1 node to also be 0 is mathematically awkward to say the least. It prevents us from from using the function to calculate a node's height based on the height of its children subtrees because - because it matters if there's 1 node there or no nodes there. Very bad definition of height. At least they should have said that a tree with no nodes has undefined height. Then you could represent that with (-1) or something.

Collectives™ on Stack Overflow

Finding max height/depth in Binary Tree

1 Answer 1

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

2. The height of the tree is 3.

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

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

2. The height of the tree is 3.

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related

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