CODEWITHSUNDEEP
javaalgorithmtree-traversal
fneron
fneron

Reputation: 1087

Algorithm traversal throughout a tree structure

Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

How would you implement objectSize to return the size in bytes of the object?

The method objectSize return the size in bytes of all children nodes combined (every node on the tree).

Example: 

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

Answer: 19+20+37+15 = 91

I had this question during an interview and I am very curious to see others answers. Since, I didn't know much about tree traversal algorithm.

I came up with this... (I know it's bad or not ;) , just trying to learn)

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

I noticed that I could have a cycle and run through a stackoverflow error, because I didn't check if I had already went trough a "node". Then I tough I should have another datastructure (like a hashmap for handling key/value) to handle temporary list for comparison.

Upvotes: 4

Views: 227

Answers (3)

Rerito
Rerito

Reputation: 6086

Here is what I would do :

I would build a stack containing the nodes that remains to be explored and process it in a while loop. Since my Java skills are lost somewhere in my mind I won't give you an implementation but I will explain the process :

Input : A tree T
Output: The total size of the node objects

  1. Initialize the stack S by pushing T.root (the root node) into it
  2. Initialize the total size size to 0 : size = 0
  3. While S is not empty :
    1. Let N be the head of S, we pop S : N = pop(S)
    2. Push N.leftChild and N.rightChild into S if they exist
    3. Update size : size = size + N.size
  4. Return size

Upvotes: 0

darijan
darijan

Reputation: 9785

I did not test it but this simple BFS search algorithm should do it.

public Long objectSize(Object object) {
   long sum=sizeOf(object);

   Queue<Object> q= new LinkedList<Object>();
   for (Object o : getRefs(object)) {
      q.add(o);
   }
   while (q.peek() != null) {
      Object child= q.poll();
      sum+= sizeOf(child);
      fore (Object o : getRefs(child)) {
         q.add(o);
      }
   }
   return sum;   
}

Upvotes: 0

Platinum Azure
Platinum Azure

Reputation: 46193

If you're dealing with a true "tree" structure, then you don't have to worry about cycles.

You've got the basic idea, but you need to take the actual return value of the recursive call into account. If we assume that the object's total size (objectSize()) is equal to the sum of the sizes of its children plus its own size (sizeOf()), then you just need to make sure you're adding all the subtree sizes together.

Here's one way you could do it:

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

    for(Object object : objectList) {
         sum += objectSize(object);
    }

    return Long.valueOf(sum);
}

The thing you were missing was that the recursive objectSize call returned a value and that value needed to be included (in this case via addition) into your return value.

Upvotes: 2

Related Questions