Algorithm traversal throughout the tree structure

Question

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 an object?

The objectSize method returns the size in bytes of all the child nodes combined (each node in the tree).

Example:

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

Answer: 19 + 20 + 37 + 15 = 91

I had this question during the interview, and I am very curious to see the answers of others. Since, I knew little about the tree traversal algorithm.

I came up with this ... (I know it is 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 might have a loop and skip the stackoverflow error, because I did not check if I already went through the "node". Then I hard must have a different data structure (for example, a hash map for processing the key / value) to process the temporary list for comparison.

Answer 1

If you are dealing with a real "tree" structure, you do not need to worry about loops.

You have a basic idea, but you need to consider the actual return value of the recursive call. Assuming the total size of the object ( objectSize() ) is equal to the sum of the sizes of its children and its own size ( sizeOf() ), then you just need to make sure that you add all the sizes of the subtree together.

Here is one way:

 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); } 

What you were missing was that the recursive call to objectSize returned a value, and that value had to be included (in this case, by adding) in your return value.

Answer 2

I have not tested 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; } 

Answer 3

Here is what I would do:

I would create a stack containing nodes that have yet to be explored and processed in a while loop . Since my Java skills are lost somewhere in my mind, I will not give you an implementation, but I will explain the process:

Entrance: Tree T
Conclusion: Total size of node objects

• Initialize the S stack by clicking on it T.root (root root)
• Initialize the total size size to 0: size = 0
• Until S is empty:
  • Let N be the head of S, we pop S: N = pop (S)
  • Press N.leftChild and N.rightChild on S if they exist.
  • Update Size: size = size + N.size
• Return size