Chapter 21, Problem 2FTE

Explanation of Solution

Given program code:

//Add a value to a binary search tree

//Return root of resulting search tree

Node add(Node tree, int value) //Line 1

{ //Line 2

    //Check if tree is equal to null

    if (tree == null) //Line 3

    { //Line 4

        //Return new node

        return new Node(x); //Line 5

//Check if the value is less than the value of the current node

        if (value < tree.value) //Line 6

            //Return and add the value to the left side

            return add (tree.left, value); //Line 7

        //Else

        else //Line 8

            //Return and add the value to the right side

            return add (tree.right, value); Line 8

}//Line 9

The above program code snippet is used to add a value to the binary search tree and the program returns the modified root value.

Error in the program code:

Error 1:

In “Line 7”, the result of the recursive call needs to be grafted back into the tree. So this line should be modified as shown below.

//Call the function "add ()" and store the resultant into the node "tree.left"

tree.left = add(tree.left, value);

//Return the node.

return tree;

Error 2:

In “Line 8”, the result of the recursive call needs to be grafted back into the tree. So this line should be modified as shown below.

//Call the function "add ()" and store the resultant into the node "tree.right"

tree.right = add(tree.right, value);

//Return the node.

return tree;   

Corrected code:

The modified code is highlighted below...