Problem with level by level tree traversal

[W@n]

Hi, i am currently working on a java assignment which require me to create a binary search tree and then get the value of the deepest node which refer to the last level of the binary search tree with level by level traversal. I did the insertion and level by level traversal but i am not sure on how to extract the node value of last level. I try counting the level of the node but the result is wrong. Pls can anyone help? I have been figuring for very long but still no outcome. Below is the attachment of my code. Or is there another way to get the deepest node? Thank in advance=D

Binary search tree created

28
      / 
    22
   /   \
  19   23
   \
   21

The deepest node value for this binary search tree is 21.

My level by level traversal code

public void topDownLevelTraversal() {
 
        if (isEmpty()) {
            return;
        }
 
        //a queue to store tree nodes
        Queue q = new Queue();
        Stack s = new Stack();
 
        //enqueue the first node
        q.enqueue(root);
        int level = 0;
        
        while (!q.isEmpty()) {
 
            BTNode cur = (BTNode)(q.dequeue());
            
            System.out.println (Integer.toString(level) + " " + cur.getItem().getAccountID());
 
            int lastlevel = level;
 
            s.push(cur);
 
            if (cur != null) {
                
 
                if (cur.getLeft() != null) {
 
                    q.enqueue(cur.getLeft());
                    level = lastlevel + 1;
 
                }
 
                if (cur.getRight() != null) {
                   
                    q.enqueue(cur.getRight());
                    level = lastlevel + 1;
                }
                
 
             }
 
        }
 
    }
    
    //Get the level of the tree
    public int height(BTNode root) {
        
        int depth = 0;
        if (root == null) {
            return 0;
        } else {
            depth = 1 + Math.max(height(root.getLeft()), 
                                 height(root.getRight()));
            
            return depth;
        }
        
    }

output of topDownLevelTraversal() method

Level = 0 - 28
Level = 1 - 22
Level = 2 - 19
Level = 3 - 23
Level = 3 - 21

According to the binary search tree i should not be getting the above result instead i should get

Level = 0 - 28
Level = 1 - 22
Level = 2 - 19
Level = 2 - 23 <== instead of level 3 it should be level 2
Level = 3 - 21

[brianlevine]

Are you familiar with recursion? It would probably simplify things for you. And it's a good thing to learn about.

But, for what you have now, your running into trouble because the "level" variable is getting incremented too often. Every time the tree branches and the branch has children then you're going to get an extra level counted.

So expanding the tree like this:

28
          /  \
        22  27
       /   \    \
     19   23  66
        \
        21

Your code will produce this:
Level = 0 - 28
Level = 1 - 22
Level = 2 - 27 <= problem because 22 has children
Level = 3 - 19
Level = 4 - 23 <= problem because 19 has children
etc.

Hope that makes sense (and that my output is correct, I did it by hand)

One option would be to create a class that stores a node and it's level, so when you traverse the children of the node, you can get the right level from it's parent.