Inserting a node into a binary search tree in C++

Question

I'm attempting to build a binary search tree and then do a horizontal inorder print with the left most node as the first node displayed. Also, preceding each node is its depth (distance from root) as well as a tilde to help visualize the tree itself. Conceptually my code seems to be correct, but for whatever reason I can't seem to get it to build the tree properly. I figure that the error is most likely in my insert function, but I can't seem to locate it.

Any suggestions or ideas would be extremely helpful!

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef struct treeNode {

    treeNode *leftChild;
    treeNode *rightChild;
    int data;
} treeNode;


void printTree(treeNode*);
int getNodeDepth(treeNode*);
treeNode* insert(treeNode*, int);
treeNode* createNewNode(int);

int main()
{


    //read in file here



    treeNode *root = NULL;

    root = insert(root, 8);
    root = insert(root, 1);
    root = insert(root, 90);
    root = insert(root, 3);
    root = insert(root, 80);
    root = insert(root, 6);
    root = insert(root, 83);

    printTree(root);

    return 0;
}


/*
 Purpose: Constructs a new node for the tree.
 Inputs:  The data for the node.
 Outputs: returns the new node
 */
treeNode* createNewNode(int data)
{
    treeNode *newNode = new treeNode;
    newNode->data = data;
    newNode->leftChild = NULL;
    newNode->rightChild = NULL;
    return newNode;
}

/*
 Purpose: Calculates the depth of a given node using recursion.
 Inputs:  The node to check the depth on.
 Outputs: returns the depth
 */
int getNodeDepth(treeNode *node)
{
    if (node == NULL)  // tree doesn't exist
        return(0);

    return(1 + max(getNodeDepth(node->leftChild), getNodeDepth(node->rightChild)));
}


/*
 Purpose: Inserts a node into the tree.
 Inputs:  The node to be inserted and the data for the node.
 Outputs: returns the inserted node
 */
treeNode* insert(treeNode *node, int data)
{
    if (node == NULL)
        return createNewNode(data);
    else
    {
        if (data <= node->data)
        {
            node->leftChild = insert(node->leftChild, data);
        }
        else
        {
            node->rightChild = insert(node->rightChild, data);
        }
        return node;
    }
}


/*
 Purpose: Prints the BST in a horizontal inorder format.
 Inputs:  The root node.
 Outputs: nothing
 */
void printTree(treeNode *node)
{
    if (node == NULL)
        return;
    printTree(node->leftChild);
    cout << "(" << (getNodeDepth(node)-1) << ") ";
    for (int i=0; i<(getNodeDepth(node)-1); i++)
        cout << "~";
    cout << node->data << endl;
    printTree(node->rightChild);
}

The current output is as follows:

(2) ~~1
(1) ~3
(0) 6
(3) ~~~8
(1) ~80
(0) 83
(2) ~~90

Obviously it can't have two roots (ie 6 and 83). Thanks!

So... you don't need the typedef struct in C++, and you would generally make those free functions class methods. Then you would have a Tree class that has the "root" node contained. — crashmstr
– crashmstr, Commented Oct 13, 2014 at 19:56
You create a memory leak right away in main(): treeNode *root = new treeNode; root = NULL; — PaulMcKenzie
– PaulMcKenzie, Commented Oct 13, 2014 at 20:52
For one, that isn't preorder; that's inorder. Preorder would dump the node, then the left, then the right. Second, the repeated depth calls are reporting the depth of the nodes under the current node; not the depth of the current node itself. A preorder print with squiggles would look something like this. — WhozCraig
– WhozCraig, Commented Oct 13, 2014 at 21:30
Search the web for examples using "c++ binary search tree example". Compare to your code. — Thomas Matthews
– Thomas Matthews, Commented Oct 13, 2014 at 21:49

alacy · Accepted Answer · 2014-10-15 19:16:26Z

For those in the future who wish for a correct implementation of the answer to my original question here is the refactored code that I came up. I decided to take an OOP approach and modified the insert and getNodeDepth function to appropriately work.

//
//  Binary Search Tree
//

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

// binary search tree
class BST {

private:
    typedef struct treeNode {
        treeNode *leftChild;
        treeNode *rightChild;
        int data;
    } treeNode;

    treeNode *root;

public:
    //Constructor
    BST() { root = NULL; }

    /*
     Purpose: Constructs a new node for the tree.
     Inputs:  The data for the node.
     Outputs: returns the new node
     */
    treeNode* createNewNode(int data)
    {
        treeNode *newNode = new treeNode;
        newNode->data = data;
        newNode->leftChild = NULL;
        newNode->rightChild = NULL;
        return newNode;
    }

    //Check if the tree is empty
    bool isEmpty() const { return root==NULL; }

    /*
     Purpose: Calculates the depth of a given node using recursion.
     Inputs:  The node to check the depth on and the node to check the depth from.
     Outputs: returns the depth
     */
    int getNodeDepth(treeNode *node, treeNode *from)
    {
        if (node == from)
            return 0;
        else if (node->data < from->data)
            return getNodeDepth(node, from->leftChild) + 1;
        else
            return getNodeDepth(node, from->rightChild) + 1;
    }


    /*
     Purpose: Inserts a node into the tree.
     Inputs:  The data for the node.
     Outputs: none
     */
    void insert(int newData)
    {
        treeNode* t = createNewNode(newData);
        treeNode* parent;
        parent = NULL;


        if(isEmpty())   //check if tree exists or not
            root = t;
        else {
            //Note: ALL insertions are as leaf nodes
            treeNode* curr;
            curr = root;
            // Find the Node's parent
            while(curr)
            {
                parent = curr;
                if (t->data > curr->data)
                    curr = curr->rightChild;
                else
                    curr = curr->leftChild;
            }

            if ((t->data) < (parent->data))
                parent->leftChild = t;
            else
                parent->rightChild = t;
        }

    }


    /*
     Purpose: Prints the BST in a horizontal inorder format.
     Inputs:  The root node.
     Outputs: nothing
     */
    void printTree(treeNode *node)
    {
        if (node == NULL)
            return;
        printTree(node->leftChild);
        cout << "(" << getNodeDepth(node, root) << ") ";
        for (int i=0; i<getNodeDepth(node, root); i++)
            cout << "~";
        cout << node->data << endl;
        printTree(node->rightChild);
    }

    //Getter for private member variable root
    void printInorder()
    {
        printTree(root);
    }

};

int main()
{
    // read file in here

    BST temp;

    temp.insert(8);
    temp.insert(1);
    temp.insert(90);
    temp.insert(3);
    temp.insert(80);
    temp.insert(6);
    temp.insert(83);

    temp.printInorder();

    return 0;
}

The correct output looks as follows with 8 as the root:

(1) ~1
(2) ~~3
(3) ~~~6
(0) 8
(2) ~~80
(3) ~~~83
(1) ~90

Hope this helps!

ipenguin · Accepted Answer · 2014-10-13 22:05:06Z

0

In the first you shouldn't write treeNode twice

typedef struct {
    treeNode *leftChild;
    treeNode *rightChild;
    int data;
} treeNode;

In the second you create a memory leak:

treeNode *root = new treeNode;
root = NULL;

You should write:

treeNode *root = NULL;

Obviously it can't have two roots (ie 6 and 83). Thanks!

6 and 83 aren't roots. 8 is a root. So your program gave right answer.

answered Oct 13, 2014 at 22:05

ipenguin

113 bronze badges

3 Comments

alacy Over a year ago

Thanks for your suggestions. I guess my problem isn't in my insert function but actually in my getNodeDepth function. According to WhozCraig above I'm not calculating the depth of the current node, but the node under that current node. Any ideas on how I can calculate the depth of that current node?

ipenguin Over a year ago

You may create new item "depth" in structure and calculate it in following way: root = 0 and if you create new node B which is son of node A, you write B.depth = A.depth + 1

alacy Over a year ago

But isn't that what I am essentially doing with my getNodeDepth function by utilizing the max math function?

Collectives™ on Stack Overflow

Inserting a node into a binary search tree in C++

2 Answers 2

Comments

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Related