This week's book giveaway is in the Cloud/Virtualization forum.
We're giving away four copies of Building Blockchain Apps and have Michael Yuan on-line!
See this thread for details.
Win a copy of Building Blockchain Apps this week in the Cloud/Virtualization forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Liutauras Vilda
  • Knute Snortum
  • Bear Bibeault
Sheriffs:
  • Devaka Cooray
  • Jeanne Boyarsky
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • salvin francis
Bartenders:
  • Tim Holloway
  • Piet Souris
  • Frits Walraven

height of a binary tree

 
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Folks,

This a homework assignment, I came up with the code in the body of the function getHeight(). I am bad at recursive functions... I also do not understand the data type "Node<E>", does it has anything to do with iterables in java? I am not asking for a solution (I know it is not appropriate) , just for someone to point me in the right direction.

 
Saloon Keeper
Posts: 6937
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Close. You'll end up in infinite recursion though (out of memory error) because you call getHeight() on itself.
 
Marshal
Posts: 6869
182
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Lazarus Wald wrote:I also do not understand the data type "Node<E>", does it has anything to do with iterables in java?


This has to do with generics in Java.  In this situation, Node<E> means basically "type Node that uses a type E", where E can be any type.  Notice that the field "data" is of type "E".
 
Sheriff
Posts: 15043
252
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It might be easier to understand recursion if you try to visualize what the code should be trying to do:

                 N0
                /  \
              N1    N2
             /  \  /  \
           N3  N4  N5  N6
          /  \        /
        N7    N8    N9
             /
           N10

The signature should be getHeight(Node<E> n) which means "Get the height of the tree with root node n". The initial call for the above tree would be getHeight(N0) which means "Get the height of the tree with root node N0." To get the height of that tree, you'd recursively "walk down" the tree to the most distant child node and see how many levels you've gone through. From N0, you have two children: N1 and N2, so you'd get the heights of each of those subtrees, which correspond to calls of getHeight(N1) and getHeight(N2). Since N1 is the left child of N0, getHeight(N1) is the same as getHeight(N0.leftChild). Similarly, getHeight(N2) is equivalent to getHeight(N0.rightChild).

If you generalize the algorithm, you're basically saying "To get the height of the tree with root node N, add 1 to the maximum of the height of the subtree whose root is leftchild (if any) and the height of the subtree whose root is rightchild (if any). So essentially, the recursion happens when you treat a child node as the root node of the next level subtree. This is what allows you to "walk down the tree" and each level you step down into (recurse into), you add 1 to the height of the tree, hence the expressions leftheight = getHeight(...) + 1; and rightheight = getHeight(...) + 1.  

As Carey said, you're close. You're just missing the reference to the node you want to treat as the root node for the current recursion level.
 
Rancher
Posts: 861
21
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lazarus,

-- recursion is calling a method from within itself, but you have to have a "halting condition", something that breaks the cycle of calling when a target value is reached.

-- Node<E> is using generics to, shown by the "<E>" to basically make everything a form of E.

-- When you use recursion without a halting condition, you recurse forever or basically until your computer runs out of memory from creating the new environments for each instance of the recursive call.

so basically, you need to make a way for your method to understand it has reach the last one, the bottom, the end leaf... where you want it to halt.  Recursion is "usually" based on the idea that you modify an argument that was supplied in the recursive call, then a check is done to see if you should stop, and if not, that argument is modified and you make another recursive call using the modified value to meet the need of the parameter of the call.

so something like this:



without the halting condition, things just go forever or until the physical limitations of your computer memory are reached.
 
Lazarus Wald
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote: This is what allows you to "walk down the tree" and each level you step down into (recurse into), you add 1 to the height of the tree, hence the expressions leftheight = getHeight(...) + 1; and rightheight = getHeight(...) + 1.  

As Carey said, you're close. You're just missing the reference to the node you want to treat as the root node for the current recursion level.



Thanks for such complete and formidable response. I tend to think that it would easier if the getHeight() function had an explicit parameter, in most algorithms that I saw it was getHeight(node).
 
Lazarus Wald
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Les Morgan, thanks for your great input. I believe that I understand the idea of a halting condition, but the only that can come to mind in this case is: if (leftChild==null && rightChild==null). I am assuming that leftChild references the current left node and rightChild references the current right node.
 
Les Morgan
Rancher
Posts: 861
21
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lazarus,

If you are looking for end, leaf nodes, then yes, all branches to the next level must be null.

A binary tree is only one instance of a family of structures called k-inary trees, you can have 2, 3, 4, ... k children off of each node, so the term is generalized to k-inary (though I do suppose you could have only 1 child off the parent and that would be a linked list).  At each level you have to remember to recurse for all non null child references and when you get to any node were all child references are null, you are at the end node/leaf.

Les

Lazarus Wald wrote:Les Morgan, thanks for your great input. I believe that I understand the idea of a halting condition, but the only that can come to mind in this case is: if (leftChild==null && rightChild==null). I am assuming that leftChild references the current left node and rightChild references the current right node.

 
Marshal
Posts: 68110
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are people talking about heights? I thought a tree had a depth.
 
Junilu Lacar
Sheriff
Posts: 15043
252
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Trees also have heights as far as I know. Leaves grow at the top of trees, too, and roots are normally at the bottom. When we talk about trees as data structures, the metaphors are all topsy-turvy anyway so why even bother distinguishing between height vs depth. it's the same difference, in my opinion.
 
Campbell Ritchie
Marshal
Posts: 68110
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, when I learnt anatomy, I had to learn that this is right ← and this is left →. Not in computer sciences, I had had to learn that this is up ↓ and this is down ↑.
 
Junilu Lacar
Sheriff
Posts: 15043
252
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I had had to learn that this is up ↓ and this is down ↑.



Classic Mac v. Windows wars: which way is scroll up/down?
 
Lazarus Wald
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got a hint from the instuctor, and then understood that I was missing the plot of the OOP nature of the code. It should be "leftheight = leftChild.getHeight()+1;" with that in mind I was able to do the second problem relatively quick. But the third problem, it is a story for another post... Thanks for all the insights!
 
Junilu Lacar
Sheriff
Posts: 15043
252
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, that would work. And it's actually more OO since a node, if always treated as a "root" of a tree, should be able to recursively figure out its height.
 
Campbell Ritchie
Marshal
Posts: 68110
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . Classic Mac v. Windows wars: which way is scroll up/down?

up = ← down = →
 
WARNING! Do not activate jet boots indoors or you will see a tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!