counting the right nodes of a binary tree

Question

I want to count the right nodes of a binary tree, for example the following one:

so I made the following program:

public class NodeT {
    int elem;
    NodeT left;
    NodeT right;
    public NodeT(int elem){
        this.elem=elem;
        left=null;
        right=null;
    }
}


public class Tree {
    public NodeT createTree(){
        NodeT root=new NodeT(15);
        NodeT n1=new NodeT(10);
        NodeT n4=new NodeT(14);
        root.left=n1;
        n1.right=n4;
        return root;
    }
 public int countRight(NodeT root){
         if (root==null) return 0;    //version 1
         else{
             return 1+countRight(root.right);
         }
     }

I called my main program in the following way:

Tree tree=new Tree();
NodeT root=tree.createTree();
System.out.println(tree.countRight(root))

This code prints 1 as the correct answer, but I cannot understand why is this happening. For what I see the right branch of 15 is equal to null so the call to the recursive function countRight() should return 0 and print an incorrect answer.

I have seen other solutions and I found that for counting all the nodes they use solutions like the following:

     static int n;
     public int countRight(NodeT root){   //version 2
         if (root==null) return 0;
         if (root.left!=null){
             n=countRight(root.left);
         }
         if (root.right!=null){
             n++;
             n=countRight(root.right);
         }
         return n;
     }

which seems more legit to me. Could it be a case in which the first version fails?

Thanks

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Jul 09 '19 at 00:15
You return ```1+countRight(root.right)``` without doing a null check on the ```root.right```. This means that even when the right node is null, you add one for it anyways. Also you never check the left side of the tree as pointed out by royalghost. To do that you need to also add a ```+countRight(root.left)``` to the return. — theawesometrey, Jul 09 '19 at 00:30

score 2 · Accepted Answer · answered Jul 09 '19 at 00:25

2

A method like that should never use a static field, or any field for that matter.

The task is to count the number of right nodes, which actually means to count the number of nodes where right is not null. You're not really counting the nodes, but the references to the nodes.

It also means you have to scan all the nodes, which means that the method must traverse both left and right.

Finally, the root node is by definition not a right node.

public int countRight(NodeT node) {
    if (node == null)
        return 0;
    if (node.right == null)
        return countRight(node.left);
    return 1 + countRight(node.left) + countRight(node.right);
}

answered Jul 09 '19 at 00:25

Andreas

154,647
11
152
247

thank you @Andreas, could you give me an example in which version 1 fails? Because when I run it, it seems that it prints the correct answer – Little Jul 09 '19 at 11:41
@Little Sure, change `root.left=n1` to `root.right=n1`. That would make node 15 be the root node, and nodes 10 and 14 would be right nodes, so 2 right nodes, but your code returns 3. --- Alternatively, change `n1.right=n4` to `n1.left=n4`. That would make nodes 10 and 14 be left nodes, so 0 right nodes, but your code returns 1. – Andreas Jul 09 '19 at 15:15

score -1 · Answer 2 · answered Jul 08 '19 at 23:07

-1

your first code will retrun 2 no way it returns 1 recursively calling

return 1+another deeper call until root.right==null

will result in 2 return based on your structure the tree you coded is different than the one you draw

answered Jul 08 '19 at 23:07

green_dust

47
4

*"no way it returns 1"* Well, question says *"This code prints 1"*, so it obviously can happen, and it does because it counts the root node, and that's it, since *"another deeper call until root.right==null"* is immediately true (hint: root.right = null). – Andreas Jul 09 '19 at 00:18
this will return 2 its obviously not 1 go it 1 doesn't equal 2 ok and the draw dosnt represent the code its totally different structure did you understand this ? – green_dust Jul 09 '19 at 01:18
The `createTree()` method creates the tree that's shown in the drawing. There are 3 nodes, with values 15, 10, and 14, so let's call them n15, n10, and n14. When you call the first version of `countRight()` with the root (n15), it will do `1 + countRight(n15.right)`. Since `n15.right` is null, that call with do `return 0`, which means the first call ends up being `return 1 + 0` and hence the final result is 1. – Andreas Jul 09 '19 at 15:18

counting the right nodes of a binary tree

2 Answers2