The complexity of space when creating an object during recursion

Question

checkIfBalanced() in the code below returns true if the tree is balanced and false otherwise. However, in each recursion, it creates a TreeData object. In my opinion, the complexity of the space is O (1), because after each frame of the stack is pushed out, the reference to the object created on this frame of the stack is lost and garbage is collected. I'm right?

Note:

• I am not looking for suggestions to improve / change my code. The following code example is designed specifically for my question.

• Also, please ignore space-complexity adding stack frames . I am looking for the spatial complexity of the created TreeData objects. It seems to me that at any moment there will be only 3 TreeData objects. What I want to check. Thanks.

  private static class TreeData { private int height; private boolean isBalanced; TreeData(int height, boolean isBalanced) { this.height = height; this.isBalanced = isBalanced; } } public boolean checkIfBalanced() { if (root == null) { throw new IllegalStateException(); } return checkBalanced(root).isBalanced; } public TreeData checkBalanced(TreeNode node) { if (node == null) return new TreeData(-1, true); TreeData tdLeft = checkBalanced(node.left); TreeData tdRight = checkBalanced(node.right); if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) { return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true); } return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false); } 

Answer 1

In my opinion, the complexity of the space is O (1), because after each frame of the stack popped up, a reference to the object created on this frame of the stack is lost and garbage. I'm right?

No, you are mistaken in assuming this. Ray Toal explained this very beautifully. At any point in the recursion, you must count all of these internal stack frames that are stored in memory, since Space-Complexity takes into account all the auxiliary space (extra space) along with input (not specified here).

Further

I am looking for the spatial complexity of the objects 'TreeData' created.

The maximum space consumed by the recursive program is proportional to the maximum depth of the recursive tree. The maximum depth of a recursion tree is defined as the length of the longest path in the tree.

For this program, the program will start from the root of the tree and first start creating the left subtree, and then check the right subtree. Finally, it will return the length of the longest path and whether the tree will be balanced OR not.

It seems to me that at any moment there will be only 3 TreeData objects. This is what I want to check.

No, at any specific runtime, all the left subtrees are checked first, and then the right subtrees are checked, so the number of TreeData objects in memory will be only 1. It will check it to the left each time OR the right child. And, therefore, all of those (log n --- in the case of a balanced tree, OR n --- in the case of a degenerate tree), but the nodes, except one, will be stored in memory. At a certain point in time, only one TreeData object will be in an active state, others will be suspended and stored in memory and waiting for their turn to pop up.

Answer 2

Here you are not using tail recursion, and you are creating stack frames when you recurse a tree. In fairness, these stack frames should be considered. If your tree is balanced, you will create stack log frames when you are recursive. In the worst case scenario, with a completely degenerate tree, you can have up to n stack frames.

Answer 3

However, in each recursion, it creates a TreeData object.

Not true. You only create a new TreeData object in the base case of your recursion. If you care, why not just add a static final instance of TreeData declared once in a class that you can use. In the end, the only thing you spread back from this Node is isBalanced boolean value.

You can also simply propagate the boolean back directly if you change your method signature to return the boolean.