BinaryTree Insert Method

Question

For class I have to create a binaryTree and I can't seem to get the insert method to work properly.

Expected results:

first: tree is not empty
        no of nodes    = 15
        height of tree =  5

The elements of 'first' in inorder:
        -11 8 -3 12 -1 -9 -5 2 16 10 6 -13 4 14 -7
The elements of 'first' in preorder:
        2 -1 -3 8 -11 12 -5 -9 4 6 10 16 -13 -7 14
The elements of 'first' in postorder:
        -11 8 12 -3 -9 -5 -1 16 10 -13 6 14 -7 4 2

second: tree is not empty
        no of nodes    =  9
        height of tree =  4

The elements of 'second' in inorder:
        7 3.25 0.75 -7.75 -0.5 -11.5 4.5 -4 8.25
The elements of 'second' in preorder:
        -0.5 0.75 3.25 7 -7.75 -4 4.5 -11.5 8.25
The elements of 'second' in postorder:
        7 3.25 -7.75 0.75 -11.5 4.5 8.25 -4 -0.5

third: tree is not empty
        no of nodes    =  7
        height of tree =  4

The elements of 'third' in inorder:
        objects. list is string This of a
The elements of 'third' in preorder:
        This is list objects. string a of
The elements of 'third' in postorder:
        objects. list string is of a This

My Results:

first: tree is not empty
       no of nodes    = 15
       height of tree = 4
The elements of 'first' in inorder:
-9 -5 4 16 -1 -13 10 -7 2 14 8 6 -3 -11 12
The elements of 'first' in preorder:
2 -1 4 -5 -9 16 -7 10 -13 -3 6 8 14 12 -11
The elements of 'first' in postorder:
-9 -5 16 4 -13 10 -7 -1 14 8 6 -11 12 -3 2
second: tree is not empty
       no of nodes    = 9
       height of tree = 3
The elements of 'second' in inorder:
-7.75 -4 0.75 -11.5 8.25 -0.5 7 4.5 3.25
The elements of 'second' in preorder:
-0.5 0.75 -4 -7.75 8.25 -11.5 3.25 4.5 7
The elements of 'second' in postorder:
-7.75 -4 -11.5 8.25 0.75 7 4.5 3.25 -0.5
third: tree is not empty
       no of nodes    = 7
       height of tree = 3
The elements of 'third' in inorder:
string a is This objects. of list
The elements of 'third' in preorder:
This is a string list of objects.
The elements of 'third' in postorder:
string a is objects. of list This

Code:

template <class T>
void binTree<T>::insert(binTreeNode < T >*& node, const T& data) {
        if(node == NULL) {
                root = new binTreeNode<T>(data, NULL, NULL);
                return;
        }

        binTreeNode<T>* ptr1 = node;
        binTreeNode<T>* ptr2 = node;
        bool placeRight = 0;
        while(ptr1 != NULL) {
                ptr2 = ptr1;
                if(height(ptr1->left) > height(ptr1->right)) {
                        placeRight = true;
                        ptr1 = ptr1->right;
                } else if (height(ptr1->right) > height(ptr1->left)) {
                        placeRight = false;
                        ptr1 = ptr1->left;
                } else {
                        placeRight = false;
                        ptr1 = ptr1->left;
                }
        }

        if(placeRight) {
                ptr2->right = new binTreeNode<T>(data, NULL, NULL);
        } else {
                ptr2->left = new binTreeNode<T>(data, NULL, NULL);
        }
}

Driver Program:

const vector<int> A { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12, 13, -14, 15 };
const vector<float> B { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25, -10.5 };
const vector<string> C { "This", "is", "a", "list", "of", "string", "objects." };
int main() {
        binTree<int> intTree = binTree<int>();
        binTree<float> floatTree = binTree<float>();
        binTree<string> strTree = binTree<string>();

        for (std::vector<int>::const_iterator it = A.begin() ; it != A.end(); ++it) {
                intTree.insert(*it);
        }
        intTree.preorder(increase);
        cout << "first: ";
        header(intTree);

        inorder(intTree, "first");
        preorder(intTree, "first");
        postOrder(intTree, "first");
}

Functions to display results: (should be correct)

template <class T>
void binTree<T>::inorder(binTreeNode < T >* node, void (*f)(T&))
{
        if (node == NULL) {
                return;
        }
        inorder(node->left,f);
        f(node->data);
        inorder(node->right,f);
}


template <class T>
void binTree<T>::preorder(binTreeNode < T >* node, void(*f)(T&))
{
        if (node == NULL) {
                return;
        }
        f(node->data);
        preorder(node->left, f);
        preorder(node->right, f);
}


template <class T>
void binTree<T>::postorder(binTreeNode < T >* node, void(*f)(T&))
{
        if (node == NULL) {
                return;
        }
        postorder(node->left, f);
        postorder(node->right, f);
        f(node->data);
}

template <class T>
    int binTree<T>::height(binTreeNode <T>* node) const {
    if (node == NULL || ((node->left == NULL) && (node->right == NULL))) {
            return 0;
    }

    int leftSide = height(node->left);
    int rightSide = height(node->right);

    if (leftSide > rightSide) {
            return leftSide + 1;
    } else {
            return rightSide + 1;
    }
}

Answer 1

Your bug is in your height method. If you have a node which is not null but has no children, you are returning zero. You should be returning 1.

Change this condition in your height method from:

if (node == NULL || ((node->left == NULL) && (node->right == NULL))) {
    return 0;
}

to:

if (node == NULL) {
    return 0;
}

Answer 2

What is your height() function ?

I think you misunderstand the definition of the BST:

A. the value of the left child is smaller than the value of root node.

B. the value of the right child is bigger than the value of root node.

C. his left child tree and right child tree are also a BST.

But through your code here:

while(ptr1 != NULL) {
            ptr2 = ptr1;
            if(height(ptr1->left) > height(ptr1->right)) {
                    placeRight = true;
                    ptr1 = ptr1->right;
            } else if (height(ptr1->right) > height(ptr1->left)) {
                    placeRight = false;
                    ptr1 = ptr1->left;
            } else {
                    placeRight = false;
                    ptr1 = ptr1->left;
            }
    }

you just compare the height of your node instead of comparing the real value of the node.

Answer 3

It appears the sign of your vector A is backwards. You have 1,-2,3,-4,... but the correct solution has -1,2,-3,4,.... Similarly, you B is

const vector<float> B { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25, -10.5 };

Comparing this with the elements you say we are expecting:

7, 3.25, 0.75, -7.75, -0.5, -11.5, 4.5, -4, 8.25

These don't look even close to identical.

Transcription error somewhere?