Need some help with binary search trees
Hey all.
The latest assignment for my Java class is this BinarySearchTree class, and one of the methods we have to include is countNodesAtLevel(int level) that takes in an int, then counts up all the nodes at that level of the tree.
I'm just having trouble thinking up a way to make this work.
My first thought was making a for loop to traverse the tree with two Node objects (one to go right, one left), but that obviously didn't work since I would wind up with two Nodes on either side of the tree with no way to go to the middle nodes.
Any ideas/code?
thanks in advance.
Do you want the nodes only on that level?
Or the nodes on it and below, or on it and above it?
If its just the nodes on it and the tree is complete.
2^level = # of nodes on that level.
With 0 equallying the root node.
1Level 0 2^0 =1
11Level 1 2^1= 2
11 11 Level 2 2^2=4
Thanks for the post, but I literally JUST figured it out.
Here's my code if you wanted to see the solution:
public int countNodesAtLevel(int level)
{
if (myRoot == null || level > this.findHeight())
return 0;
int curTotal = countLevelHelper(myRoot, level, 0);
return this.countAllNodes() - curTotal;
}
//countNodesAtLevel helper
private int countLevelHelper (BinaryTreeNode root, int level, int start)
{
/*
* Basically, this method counts up all nodes going up to the level desired,
* then SKIPS the current level the count the last levels.
* That way, the original method can simply take all nodes and subtract for the
* desired answer
*/
if (root == null)
return 0;
if (level > this.findHeight() || start > this.findHeight())
return 0;
if (level == start)
return countLevelHelper(root.left, level, start + 1) + countLevelHelper(root.right, level, start + 1);
else
{
return 1 + countLevelHelper(root.left, level, start + 1) + countLevelHelper(root.right, level, start + 1);
}
}
I realize I can clean it up a bit (mainly the original method doesn't need the error-checking since I put it in the helper.
