0

I was asked to provide the size of this Node in a binary tree.

Here is a simple Node class.

class Node {
   Integer data;
   Node left, right;
}

Node integerNode = new Node(1000);
integerNode.left=someIntegerNode1;
integerNode.right=someIntegerNode2;

Given Node has some data and both left and right references are not null. How would you calculate the size of integerNode?

This problem was then extended to Node class that contains a Person data like below:

class Node {
   Person data;
   Node left, right;
}
Node personNode = new Node(someHeavyPersonObject);
personNode.left=somePersonNode1;
personNode.right=somePersonNode2;

Assume that node is completely filled and Person object may be very heavy object.

Does both integerNode and personNode have different sizes or same?

These are the two ways I can think of:

  1. Node's size doesn't matter as it holds just the references and not the actual data object. So it would always occupy the size equivalent to three references(data, left and right).
  2. Node's size depends upon the data object it holds.

I've looked into this question In Java, what is the best way to determine the size of an object? but it seems unrelated as I am looking for the logic for computing size (not actual size) without using any libraries like java.lang.instrument.Instrumentation.

Thanks in advance!!!

Shanu Gupta
  • 3,699
  • 2
  • 19
  • 29
  • 1
    What do you mean with size exactly? Number of bytes your code compiles to? Bytesize in terms of "one int is 4 byte, 2 ints are 8 byte" etc.? – Ben Jun 14 '18 at 06:54
  • @Ben By `size` I mean the one which it would occupy when its loaded in the main memory /ram. – Shanu Gupta Jun 14 '18 at 06:59

1 Answers1

1

This is a typical interview question that is trying to determine if you fully understand how Java uses references and objects.

A good answer might be something like:

The tree node itself would only take up as much space as the references it holds, in this case the space take by just 3 references. This allows Java objects to reside in different structures at the same time without taking more space.

OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • Makes sense to me. But what if I generate 10000 random Integer objects at run time and create Nodes out of it? Wouldn't that be a part of node size? – Shanu Gupta Jun 14 '18 at 07:08
  • @ShanuGupta - Yes and no - and it is this duality that someone with a clear understanding of Java would be able to explain. The tree itself would still use `3 * 10_000` space while the random numbers would take up another `10_000` making the total memory taken as `4 * 10_000`. – OldCurmudgeon Jun 14 '18 at 07:21