• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Getting the height of a binary tree

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


I do not understand how " height(root.left) or height(root.right) " returns an integer.
can someone help me to understand, please?

 
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Break it down into smaller pieces. You also needed to see if you were at  the end of a branch.
 
Marshal
Posts: 79177
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

I thought it was supposed to be called, “depth.” Also I think that the parameter root is poorly named because you won't always call that method on the root node.
Who gave you that code? Did they tell you it is incorrect?
That looks like a recursive function. What you are doing is finding the depth of your root Node. So you look at the left, and that has a depth, and you look on the right, and that has a depth. Now, you work out which is larger, which you can either do with the expression (i > j ? i : j) or Math.max(i, j), which actually does the same. Then you add one because you have gone one level down into the tree.
Then you do the same for the left branch and the right branch, and all works well until you get to a node which isn't a branching node with both left and right branches. Then one or other branch's absence is represented by a null. It won't take you long to find a null, because a binary tree contains one more null than it contains nodes. At which point it becomes impossible to call the height() method and you have an Exception thrown.
* * * * * * * * * * * * * * * * *
In order to get recursion to work, you need a “base case.” That is where the recursion stops and some default value is returned from the method. If you don't stop the recursion, it will keep going until something goes wrong, e.g., you exhaust stack memory or some other essential resource. 0 is a common base case return value.
You need to allow for the possibility of nulls. I shall use the ?: operator for that.I gave that method private access assuming that Node is a nested class inside BinaryTree. The enclosing class has access to private members of its nested classes.
Since every path through a binary tree eventually leads to a null, you will eventually hit your base case, where the depth comes to 0.
Since every node has left and right fields, you don't need to pass arguments to that method.
Since the depth of an empty tree, a tree whose root node is null is 0, you will have to arrange to call that method such that it gives 0 for a completely empty tree, which is quite easy if the two classes are nested.
 
Allan Collado
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I understand about the base case. I omitted it because i just wanted to know what is the value that height(root.left) return? I know it will return an integer but i don’t understand how it’s that possible if  i am passing an object as parameter.
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The type of the return (if any) is not constrained by the type(s) of the parameter(s). Your recursive method follows a branch down the tree until it reaches null, then that call returns 0, and the previous call returns 0+1 etc.
 
Allan Collado
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That means every time that the recursive reach a node it will count 1 and when the recursive stop it will count what is in the call stack?
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes. As the call stack unwinds the count gets incremented and passed up to the previous call. At each stage max() is used to determine which branch, left or right, had the deepest count.
 
Allan Collado
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you very much! I got it now 🥹
 
Carey Brown
Saloon Keeper
Posts: 10705
86
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Glad I could help. Thanks for the  "thumbs up".
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I thought it was supposed to be called, “depth.”


The height and the depth of a node in a tree are two very different properties.

A node's depth is how many ancestors a node has. Allan is looking for the height, which is how many generations of descendants a node has.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you, Stephan
 
reply
    Bookmark Topic Watch Topic
  • New Topic