• 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
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Bear Bibeault
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • salvin francis
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Frits Walraven
Bartenders:
  • Jj Roberts
  • Carey Brown
  • Scott Selikoff

Storing Parent child relationship in a tree and finding its depth

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
I am trying to create a tree implementation to store the parent child relationship.I need to find out depth of that tree.
Tree implementation is of the form.


Am i doing it correct.Do i need a reference to parent node or only this will do.

A node can have multiple leaf nodes so an instance of testTree will have a list containing many instances of same type which are its children and so forth for every object in the leaf.

Now i need to find the maximum depth in the tree.
I understand i will have to use some kind of recursion to achieve this but not able to visualize it algorithmic-ally.Any pointers?

Also any better data structures .My motive is to find maximum depth of the relation.

Regards,
Sourabh
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When I think about recursion, I like to think about the end condition first, and figure out what I want to do. In pseudo-english, I think I would say the condition and procedure would be:

If the node has no children, return 1 as the depth, the 1 representing this node.


Then I think about what I should do when it isn't the end condition:

Otherwise, find the depth of each child node. Keep the maximum of the returned values (the deepest child). Then add 1 to the depth of the children to represent this node's layer, and return the result.


If those statements make sense and seem to cover all the conditions I would then translate them into code - but I will leave that task to you.
 
s sarma
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How about this.??
Any suggestions/corrections
 
Marshal
Posts: 72106
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

s sarma wrote:How about this.??
Any suggestions/corrections . . .

How did you work that code out? Did you consider the structure of a binary tree, and which node is which. What does the method you are invoking return?

That is what you need to do to get a depth method which actually works. If you don’t consider its structure, you won’t get code that works.
 
Sheriff
Posts: 16081
267
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comment on logic:
- You are going to be returning the depth of the last element because line 15 always replaces the current value of 'x'; this will give you the wrong result

Comments on form:
- You implement this as a static method. This would be more object-oriented if you implement it as a method of the 'testTree' class such that you can have code like this:
int depth = myTree.depth();
instead of int depth = depth(myTree);

- 'testTree' does not follow the normal naming convention for Java classes. Prefer 'TestTree' instead. The name 'testTree' itself is not a very good one but if this is only "play" code then it's not a big deal

- the variable name 'tempPoint' is not very good either. Names should reveal the intent or purpose of something. The children of a tree are generally referred to as "leaf" nodes, so 'leaf' might be a better variable name.

- the declared type of the 'tempPoint' variable is 'testTree' and yet you cast the value returned by it.next() to type Point. Is Point a subclass of testTree? Not clear from what you gave but that's a bit convoluted. Again, it may be a problem with the names you are using not revealing the intent very well.

 
Bartender
Posts: 1111
Eclipse IDE Oracle VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Steve Luke wrote:When I think about recursion, I like to think about the end condition first, and figure out what I want to do. In pseudo-english, I think I would say the condition and procedure would be:

If the node has no children, return 1 as the depth, the 1 representing this node.


Then I think about what I should do when it isn't the end condition:

Otherwise, find the depth of each child node. Keep the maximum of the returned values (the deepest child). Then add 1 to the depth of the children to represent this node's layer, and return the result.


If those statements make sense and seem to cover all the conditions I would then translate them into code - but I will leave that task to you.



My lecturer at college said "the first line of a recursive function you write is the exit condition"! Still do it 25 years later.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic