I\'m having trouble with my BuildBST Function. package bstpractice; import java.

Question

I'm having trouble with my BuildBST Function. package bstpractice; import java.io.*; import java.util.*; class Node { public String name; //data[low] or data[high] are the data items represented by the subtree //data[mid] is the lowIndx+highIndx +1 / 2 public int lowIndx, highIndx, leftChildIndx, rightChildIndx; public Node(int lowIndx, int highIndx, int leftChildIndx, int rightChildIndx){ this.lowIndx = lowIndx; this.highIndx = highIndx; this.leftChildIndx = leftChildIndx; this.rightChildIndx = rightChildIndx; } public String toString(){ return("lowIndx=" + lowIndx + " highIndx=" + highIndx + ((leftChildIndx >= 0) ? ("leftChildIndx=" + leftChildIndx) : "") + ((rightChildIndx >= 0) ? ( "rightChildIndx=" + rightChildIndx) : "")); } } public class BSTpractice { int root; int [] data = {-3, 2, 11, 12, 18, 23, 31, 32, 35, 42, 44}; Node[] nodes; public BSTpractice(int numNodes){ nodes = new Node[numNodes]; root = BuildBST(0, numNodes-1); } //This is the function im having problems with. //This is supposed to be a recursive function, that returns the root node num. //His example is: nodes[1]: lowIndx=0 highIndx=1 leftChildIndx=0 private int BuildBST(int low, int high){ int root = (low + high +1)/ 2; if(low == high); else if(low < root){ if(low SearchPath(int startIndx, int endIndx, int x){ ArrayList searchPathDataIndices = new ArrayList(); int origStartIndx = startIndx, origEdIndx = endIndx; //this while-loop will all the loop to be terminated immediately after the test fails. while (startIndx <=x){ if (startIndx == x); else if (startIndx < x){ searchPathDataIndices.add(endIndx,x); x++; } else if(startIndx > x){ searchPathDataIndices.add(startIndx,x); } } return (searchPathDataIndices); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int numNodes = 9; BSTpractice bst = new BSTpractice(numNodes); System.out.println(); System.out.print("data[]: " + Arrays.toString(bst.data)); System.out.println(" (only the first " + numNodes + "items used)"); System.out.print("Hit return-key to continue successive runs of SearchPath:"); scan.nextLine(); bst.SearchPath(0, numNodes-1, 12); scan.nextLine(); bst.SearchPath(0, numNodes-1, 20); scan.nextLine(); bst.SearchPath(0, numNodes-1, 10); scan.nextLine(); bst.SearchPath(0, numNodes-1, -5); scan.nextLine(); bst.SearchPath(0, numNodes-1, 43); scan.nextLine(); bst.SearchPath(0, numNodes-1, 32); scan.nextLine(); } }

Explanation / Answer

I assume the data array will always be sorted, and the goal is to make a balanced BST.

//This is the function im having problems with.
//This is supposed to be a recursive function, that returns the root node num.
//His example is: nodes[1]: lowIndx=0 highIndx=1 leftChildIndx=0


private int BuildBST(int low, int high)
{
// break condition
if(low > high)
{
return -1;
}

// otherwise, divide and conquer
int mid = (low+high)/2;

int lowIndx = BuildBST(low, mid-1);
int highIndx = BuildBST(mid+1, high);

nodes[mid] = new Node(lowIndx, highIndx, lowIndx, highIndx);

return mid;
}

I have included the following test methods to verify the BST is built correctly. You can call these in main().

private void printNodes()
{
System.out.println();
for(int i = 0; i < nodes.length; i++)
{
if(nodes[i] == null)
{
System.out.println(i+" null");
}
else
System.out.println(i+" "+nodes[i].lowIndx+" "+nodes[i].highIndx+" "+nodes[i].leftChildIndx+" "+nodes[i].rightChildIndx);
}
System.out.println();
}

// traversal
private void inOrder()
{
inOrder(root);
}
private void inOrder(int node)
{
System.out.println();
if(nodes[node].leftChildIndx >= 0)
{
inOrder(nodes[node].leftChildIndx);
}
System.out.print(data[node]+" ");
if(nodes[node].rightChildIndx >= 0)
{
inOrder(nodes[node].rightChildIndx);
}
System.out.println();
}

__________________

public static void main(String[] args)
{
int numNodes = 9;

BSTpractice bst = new BSTpractice(numNodes);

System.out.println();

System.out.print("data[]: " + Arrays.toString(bst.data));

bst.printNodes();
bst.inOrder();

System.out.println(" (only the first " + numNodes + "items used)");
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.