• Post Reply Bookmark Topic Watch Topic
  • New Topic

Storing Parent child relationship in a tree and finding its depth  RSS feed

 
s sarma
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • 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
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
How about this.??
Any suggestions/corrections
 
Campbell Ritchie
Marshal
Posts: 56581
172
  • Mark post as helpful
  • send pies
  • 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.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • 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.

 
Wendy L Gibbons
Bartender
Posts: 1111
Eclipse IDE Oracle VI Editor
  • Mark post as helpful
  • send pies
  • 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.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!