File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes The level of a Node in a Binary Tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "The level of a Node in a Binary Tree" Watch "The level of a Node in a Binary Tree" New topic
Author

The level of a Node in a Binary Tree

Antonio Nobrega
Greenhorn

Joined: Apr 05, 2010
Posts: 11
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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

    Joined: Apr 05, 2010
    Posts: 11
    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
    Bartender

    Joined: Oct 14, 2005
    Posts: 18541
        
        8

    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

    Joined: Apr 05, 2010
    Posts: 11
    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

    Joined: Apr 05, 2010
    Posts: 11
    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

    Joined: Oct 13, 2005
    Posts: 37958
        
      22
    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

    Joined: Apr 05, 2010
    Posts: 11
    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

    Joined: Oct 13, 2005
    Posts: 37958
        
      22
    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

    Joined: Apr 05, 2010
    Posts: 11
    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

    Joined: Sep 20, 2010
    Posts: 3582
        
      14

    Antonio, do you know how recursion works? If not, you should do a search for it.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 37958
        
      22
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: The level of a Node in a Binary Tree
     
    Similar Threads
    Inorder traversal of a Binary Search Tree
    Deleting all leaves from a binary tree
    searching method for a Binary Search Tree
    Traversing the right branch of a binary tree.
    mistake