scraig scraig - 12 days ago 8
Java Question

How to keep a count through a recursive method when trying to fill an array in a BST

I'm trying to fill an array in through a preorder tree traversal, but I think I've made a mistake with how to keep the counter correct. My toString() method calls on the preorder method, but it just outputs null. How can I fix this?

public AVLTreeNode[] preorder()
{
/*
* return an array of AVLTreeNodes in preorder
*/
AVLTreeNode[] preorder = new AVLTreeNode[size];
int count = 0;
return preorder(root, count, preorder);
}

private AVLTreeNode[] preorder(AVLTreeNode data, int count, AVLTreeNode preorder[])
{
if (data == null)
{
return preorder;
}
preorder[count] = data;
if (data.getLeft() != null)
{
preorder(data.getLeft(), count++, preorder);
}
if (data.getRight() != null)
{
preorder(data.getRight(), count++, preorder);
}
return preorder;
}

Answer

count has the wrong value because on subsequent calls of preorder with count++ the actual value of count is passed to the method and afterwards count is increased. Also after returning from the left node count has probably a higher value than what you pass to the call for the right node. There are two solutions:

  1. Use a global private int count; and set it to 0 before calling preorder.

  2. Return the new count instead of the AVLTreeNode[] and assign it to the local count of the method to get the correct value. AVLTreeNode[] preorder could also be a private variable.