# IndexOf recursion problem

• 03-28-2012, 02:24 AM
CeciliaP
IndexOf recursion problem
Hi I am currently trying to weight-balance a Binary Search Tree by creating new trees out of the left and right subtree of a tree that is weight balanced at the root. Any ways, the code for some reason goes to the right first, which I do not understand, and I am running into an error in using java's indexOf method. Nodes is an ArrayList kept outside of the method I posted, and any time the method recurses, the IndexOf returns -1 for the index of the new median, even though it is clearly still in the list. I passed in a sorted list 1-9
it found the median of 5, then recursed, and found the new median to be 7, I printed out the sixth index, it was seven, I printed out nodes.indexOf(root) and it gave -1. Can anyone tell me whats going on.

Code:

public BinaryNode<AnyType> balance(BinarySearchTree<AnyType> tree, int level){
if(tree.root.left == null && tree.root. right == null){
return null;
}
else{
BinarySearchTree<AnyType> newTree = new BinarySearchTree<AnyType>();
root = tree.median();
System.out.println(root.element + " is the supposed median");
newTree.insert(root.element);
System.out.println(newTree.root.element+ " is the new tree root");
for(int i = 0; i<nodes.size(); i++){
newTree.insert(nodes.get(i).element);
}
BinarySearchTree<AnyType> leftTree = new BinarySearchTree<AnyType>();
BinarySearchTree<AnyType> rightTree = new BinarySearchTree<AnyType>();
System.out.println(nodes.indexOf(root)+" is the index of the median printed out");
System.out.println(nodes.get(6).element+ " the sixth index");
for(int i = 0; i<nodes.indexOf(root); i++){
leftTree.insert(nodes.get(i).element);
}
for(int i = nodes.indexOf(root); i<nodes.size(); i++){
rightTree.insert(nodes.get(i).element);
}
if(root.left != null){
System.out.println("Left, Level: "+level);

root.left = balance(leftTree, level+1);
}
if(root.right != null){
System.out.println("Right, Level: "+level);

root.right = balance(rightTree, level+1);
}
}
return root;
}

• 03-28-2012, 02:36 AM
doWhile
Re: IndexOf recursion problem
What is BinarySearchTree? A List is one dimensional...a binary tree 2 dimensional. Are you sure the list of nodes within this class captures the 2-dim structure of the binary tree? (in other words, are you sure the nodes returned by getNodes are ordered as you expect?)
• 03-28-2012, 02:44 AM
CeciliaP
Re: IndexOf recursion problem
I apologize for being unclear. I am simply keeping track of the inorder representation of the tree passed in to the method originally. It is a sorted list. Then I use the insert method to add those elements into the BST , thus turning them into nodes. And when I asaid I passed in a list with the sixth index as the second median, I mean when I called the method, I used a list that had that as the second median, not that I already knew the values before I called anything.

In short I am sure all elements are successfully implemented into a Binary Search Tree as BinaryNodes.