java - Size of the node of a binary tree in java

Question

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!!!

标签： javaalgorithmdata-structuressizebinary-tree

Answer 1

这是一个典型的面试问题，试图确定您是否完全了解 Java 如何使用引用和对象。

一个好的答案可能是这样的：

树节点本身只占用它所拥有的引用的空间，在这种情况下，空间只占用3 个引用。这允许 Java 对象同时驻留在不同的结构中，而不会占用更多空间。