CODEWITHSUNDEEP
javatree
ron8
ron8

Reputation: 243

Find the position of all leaves in tree (JAVA)

Lets assume that I have a tree as like below:

     O
    / \
   O   \
  / \   \
 A   B   C

How would I go about finding the position of all the leaves in this tree and output them in an array or HashMap?

So the above tree would return:

{{  A   ,     00      },{  B   ,     01      },{  C   ,   1   }}
   leaf    left, left     leaf   left, right     leaf   right

I was thinking to iterate down the tree until it found a leaf and remember which path it took. But I am not quite sure whether this is the most efficient way of doing this.

Any ideas how this could be implemented?

Upvotes: 0

Views: 143

Answers (1)

BambooleanLogic
BambooleanLogic

Reputation: 8161

Assuming that there's no already existing metadata that can be used, the easiest solution is probably just a regular Depth-First search with a stack containing the path taken so far. I don't see how one could do it in a significantly more efficient way.

Upvotes: 2

Related Questions