Binary Search Tree using recursion in Java

Question

I am hoping someone can give me an explanation of how I am supposed to finish these two methods. I am willing to do the work myself and am not trying to be lazy. Having said that, here is the problem:

2 methods: Recursively need to

count the number of nodes in a binary tree,
count the number of right children

I have already implemented the following code:

public class IntBSTNode
{

    protected int key;
    protected IntBSTNode left, right;

    public IntBSTNode()
    {
        left = right =null;
    }

    public IntBSTNode(int el)
    {
        this(el, null, null);
    }

    public IntBSTNode( int el, IntBSTNode lt, IntBSTNode rt)
    {
        key = el;
        left =lt;
        right = rt;
    }
}

Yeah I'm assuming homework too. To get you started, think about putting a method on IntBSTNode which returned the number of children of the sub nodes, plus the number of children on this node. — AdamH
– AdamH, Commented Mar 9, 2011 at 2:53
So far, you've only written the constructors. Did you even attempt to write the recursive methods? What did you try? What didn't work about it? — Matt Ball
– Matt Ball, Commented Mar 9, 2011 at 2:59

dting · Accepted Answer · 2011-03-09 07:43:04Z

http://en.wikipedia.org/wiki/Recursion

For recursion to work you need a base case, and a set of cases and actions that reduce towards the base case.

For counting the number of nodes in a binary trees, we can use the base case of "a node does not exists", and other case of "a node does exist".

For the other case, (node does exist) we will add 1 to the count of nodes add the number of nodes in each of the tree's subtrees (left and right) to the total count. How do we find the number of nodes in the subtrees? Simply apply the same set of conditions that we used for the first node to the child nodes.

By repeatedly breaking down the tree's subnodes we can obtain the total number of nodes in the tree

Take for example:

     N1
     /\ 
   N2   N3
   /\    \
 N4  N5   N6

Let's call our counting method countNodes().

pseudocode for countNodes

int countNodes(Node parent):
    if parent:
        return 1 + countNodes(parent.left) + countNodes(parent.right)
    else:
        return 0

countNodes will first check if the node you pass to it exists.

If not (base case) return 0 [logically this makes sense because if the node doesnt exist, there will be no nodes in it's subtree's that dont exist]

If the node exists you will return 1 + the sum of the number of nodes in the subtrees. To find the number of nodes in the subtrees we will just call our countNodes() method on each child node.

In the example tree above we start with N1. We see that N1 exists so what we need to find now is:

1 + # of nodes in the left subtree + # of nodes in the right subtree.

N1's subtrees are:

  Left         Right
   N2            N3
   /\             \
 N4  N5            N6

We start by calling the countNodes() method on N2 (N1's left subtree).

N2 exists so now we are looking for

1 + # of nodes in N2's left subtree + # of nodes in N2's right subtree

N2's subtrees are:

Left     Right
 N4       N5

calling countNodes() on N4 we are looking for

1 + # of nodes in N4's left subtree + # of nodes in N4's right subtree

N4's left node is null so when countNodes() is called on N4's left node it will return 0 (base case).

N4's right node is also null so countNodes() for the right node is also going to return 0

N4's pending operations can complete and you have 1 + 0 + 0 (non-base case return value)

Now N2's pending operation looks like

1 + 1 + # of nodes right subtree

calling countNodes() on N5 results in the same value as N4 so N2's return value has become:

1 + 1 + 1

N2 returns 3 to N1's pending operation to make it look like:

1 + 3 + # nodes in right subtree

# nodes in N3 subtree is:
countNodes() on N3 returns 1 + countNodes->null (base) + countNodes()->N6

# nodes in N6 subtree is
countNodes() on N6 returns 1 + countNodes->null (base) + countNodes()->null (base)
return value = 1

# nodes in N3 subtree is 1 + 0 + 1
returns 2

finally the call on N1's countNodes() can complete with 

1 + 3 + 2

countNodes() on N1 returns 6

To count all the right nodes in a tree you can use the following pseudocode:

int countRightNodes(Node parent):
    if !parent:
        return 0

    if has right node:
        return 1 + (# of right nodes in left subtree) + (# of right nodes in right subtree)
    else:
        return (# of right nodes in left subtree)

nbarraille · Accepted Answer · 2011-03-09 03:59:03Z

2

The point of recursion, is to simplify a complicated problem until it is trivial, and use the solution of this trivial problem to find the solution of a more complicated problem, etc, until you can solve your actual problem.

In your case 1), the complicated problem is "Find the number of nodes in the whole tree". But we can simplify this, by saying that it is numberOfNodesLeftSubtree + numberOfNodesRightSubtree + 1. We can then write:

public int nbNodes(Node root){
    int count = 1 // our actual node
    if(root.left != null){
        count += nbNodes(root.left);
    }
    if(root.right != null){
        count += nbNodes(root.right);
    }

    return count;
}

It's that easy.

answered Mar 9, 2011 at 3:59

nbarraille

10.1k14 gold badges68 silver badges94 bronze badges

1 Comment

claudio495h Over a year ago

a recent pet peeve of mine, why write countNodes(root); instead of root.countNodes();

Michael McGowan · Accepted Answer · 2011-03-09 02:59:27Z

0

Thinking recursively takes some practice, but it almost seems magical when done well. We need to count the number of nodes in our tree, so let's think what that means. Consider any node and it's sub-tree. The number of nodes in this sub-tree will be equal to the number of nodes in the left sub-tree plus the number of nodes in the right sub-tree, plus one (for the node in question). So if we assume we already had a method that could count nodes in a sub-tree, we could make two calls to that method. We also have to worry about the base case, and then once we have that recursion can work its magic.

answered Mar 9, 2011 at 2:59

Michael McGowan

6,6168 gold badges45 silver badges70 bronze badges

Collectives™ on Stack Overflow

Binary Search Tree using recursion in Java

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related