Simple binary tree question

Question

I was wanting to display all of the nodes at a certain level in the tree:

Called by: allNodesAtACertainLevel(0, *whatever level you want*, root);

This produces the correct answer.

private void allNodesAtACertainLevel(int count, int level, Node n){

        count += 1;

        if(count <= level){
            if(n.left != null) allNodesAtACertainLevel(count, level, n.left);
            if(n.right != null) allNodesAtACertainLevel(count, level, n.right);
        }
        else{
            System.out.print(n.value);
        }

    }

This doesn't.

private void allNodesAtACertainLevel(int count, int level, Node n){

        if(count < level){
            if(n.left != null) allNodesAtACertainLevel(count++, level, n.left);
            if(n.right != null) allNodesAtACertainLevel(count++, level, n.right);
        }
        else{
            System.out.print(n.value);
        }

    }

Could someone explain why?

Mark Elliot · Accepted Answer · 2011-02-23 02:33:16Z

6

The second example increments count twice, the first example increments count only once. Also the first increments count before calls to allNodesAtACertainLevel while second example calls allNodesAtACertainLevel and increments count after the call.

Any of these should produce a correct result when substituted appropriately for the second example:

count++;
if(n.left != null) allNodesAtACertainLevel(count, level, n.left);
if(n.right != null) allNodesAtACertainLevel(count, level, n.right);

--

count += 1;
if(n.left != null) allNodesAtACertainLevel(count, level, n.left);
if(n.right != null) allNodesAtACertainLevel(count, level, n.right);

--

if(n.left != null) allNodesAtACertainLevel(count+1, level, n.left);
if(n.right != null) allNodesAtACertainLevel(count+1, level, n.right);

edited Feb 23, 2011 at 2:33

answered Feb 23, 2011 at 2:27

Mark Elliot

77.4k23 gold badges147 silver badges162 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ryan Over a year ago

I thought it would only increment the value within the scope of the respective recursive call.

Mark Elliot Over a year ago

@Ryan: It increments it within the scope of the variable, not in the call. I've added some equivalent versions, the last is likely what you were really going for.

Ryan Over a year ago

You're correct, the last example is what I thought would be happening. Thank you for the explanation!

Lucas S. · Accepted Answer · 2011-02-23 02:38:05Z

2

Your problem is because you are making count++ to times, so you increment the level counter one extra time.

You should change your code to the following:

count++;
if(n.left != null) allNodesAtACertainLevel(count, level, n.left);
if(n.right != null) allNodesAtACertainLevel(count, level, n.right);

edited Feb 23, 2011 at 2:38

answered Feb 23, 2011 at 2:30

Lucas S.

13.6k9 gold badges49 silver badges46 bronze badges

2 Comments

Ryan Over a year ago

Wouldn't this return an incorrect answer if the left node were ever null and the right node wasn't?

Lucas S. Over a year ago

You are right, i have missed the one-liner if statement, corrected now.

Collectives™ on Stack Overflow

Simple binary tree question

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related