• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

The level of a Node in a Binary Tree

 
Antonio Nobrega
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I'm having a big problem while trying to find the error here. My assigment is basically to implement a binary tree , which i thought i did, until i was told that i was going to need a method to calculate the level of a node.
I have tried for a couple days now and, i dont know if i am just too tired, i cant find the answer to it. Here's my binary tree :

Node Class:




Thats how i tried to do it : I added an attribute to the node class called Level.


So, what i did was increment the level every time i "went down to the left or to the right" of the tree. But it isnt working on all cases. Do you guys see anything wrong?
The method i called Comparar, basically returns the higher value node.
The method buscarn is a search method, it returns the node if the node exists in the binary tree, or null if it doesnt.

PS: Don't mind about the return values, the assigment iself is to build some sort of agenda and to make things more organized on the main method, the insert method already returns the String i have to print on the file.
PS²: Sorry for my poor english.
PS³: Thanks in advance.
 
Paul Clapham
Sheriff
Pie
Posts: 20739
30
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know why your code is not doing what you want. But you shouldn't want that anyway. You shouldn't have to store the level in the node. Instead, here's how you find the level of a node:

  • If the node is the root, then its level is one. Or zero, if that's how you count.
  • If the node is not the root, then its level is one greater than the level of its parent.
  •  
    Antonio Nobrega
    Greenhorn
    Posts: 11
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Paul Clapham wrote:I don't know why your code is not doing what you want. But you shouldn't want that anyway. You shouldn't have to store the level in the node. Instead, here's how you find the level of a node:

  • If the node is the root, then its level is one. Or zero, if that's how you count.
  • If the node is not the root, then its level is one greater than the level of its parent.


  • Hmm..Ok so should i create a method to do that and return the level instead of storing the level in the node?
    Also, why shouldnt i store the level?
     
    Paul Clapham
    Sheriff
    Pie
    Posts: 20739
    30
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Antonio Nobrega wrote:Hmm..Ok so should i create a method to do that and return the level instead of storing the level in the node?
    Also, why shouldnt i store the level?


    That's what I would do. If you store the level in the node, then when you move the node to a different place in the tree, you have to recalculate the level. That's just error-prone. You already found out that trying to store the level in the node was error-prone, didn't you?
     
    Antonio Nobrega
    Greenhorn
    Posts: 11
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Paul Clapham wrote:
    Antonio Nobrega wrote:Hmm..Ok so should i create a method to do that and return the level instead of storing the level in the node?
    Also, why shouldnt i store the level?


    That's what I would do. If you store the level in the node, then when you move the node to a different place in the tree, you have to recalculate the level. That's just error-prone. You already found out that trying to store the level in the node was error-prone, didn't you?


    Yeah i did. Thank you very much for your help. ^^

     
    Antonio Nobrega
    Greenhorn
    Posts: 11
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I am really sorry to re-open this topic, but i need some more help.
    So, im trying to implement a getLevel method. Here's the problem, i thought it was working just fine until i tested it with a bigger tree. It's not working properly and i cant find the error, i tried to debug it but it only doesnt work when i try it with a really big tree.

    Just to remember that the comparar(node,node) method, returns the node that has the bigger key in it.


     
    Campbell Ritchie
    Sheriff
    Posts: 48382
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Your comparar method which takes two nodes is dangerous. Since trees can contain null nodes, that may suffer an Exception.
    Your getLevel method appears to change the structure of the tree, which also appears dangerous.
    I would do it by recursion myself.
     
    Antonio Nobrega
    Greenhorn
    Posts: 11
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:Your comparar method which takes two nodes is dangerous. Since trees can contain null nodes, that may suffer an Exception.
    Your getLevel method appears to change the structure of the tree, which also appears dangerous.
    I would do it by recursion myself.


    I'm making sure the comparar method never tries to compare something to a null node.
    Also, the getLevel doesnt change anything, you can see that i use root and this.root, where this.root is the attribute of the tree, while root is just a node i created to help me find the level.
    Any hints on how to do the getLevel method instead?
     
    Campbell Ritchie
    Sheriff
    Posts: 48382
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    yes, there are some hints:
    Paul Clapham wrote:# If the node is the root, then its level is one. Or zero, if that's how you count.
    # If the node is not the root, then its level is one greater than the level of its parent.
    I earlier wrote:I would do it by recursion myself.


    And I now see your method uses local variables, so it doesn't actually change the tree. But the use of shadowing local variables is dubious, and that method is unnecessarily complicated.
     
    Antonio Nobrega
    Greenhorn
    Posts: 11
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Campbell Ritchie wrote:yes, there are some hints:
    Paul Clapham wrote:# If the node is the root, then its level is one. Or zero, if that's how you count.
    # If the node is not the root, then its level is one greater than the level of its parent.
    I earlier wrote:I would do it by recursion myself.


    And I now see your method uses local variables, so it doesn't actually change the tree. But the use of shadowing local variables is dubious, and that method is unnecessarily complicated.


    Hmm yeah i get what you're saying. Could you help me implement a method that actually works? Cause this one is failing.
     
    Stephan van Hulst
    Bartender
    Pie
    Posts: 5349
    50
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Antonio, do you know how recursion works? If not, you should do a search for it.
     
    Campbell Ritchie
    Sheriff
    Posts: 48382
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    A node doesn't know which level it is at. But it can return a depth (maybe 1: see what I quoted from Paul C's post yesterday) if its "value" is the same as the sought value. If the sought value is "less than" is value, the depth is 1 more than the depth reported by its "left" branch, or similarly for "more than" and right branch.

    If the value sought is "greater than" the value and the "right" branch is null, you can either throw an Exception or return a nonsense value, for example Integer.MIN_VALUE. Similarly for "less than" and "left" branch is null.
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic