Binary search tree printing out incorrect height

[darego]

I am trying to create a simple Binary Search Tree, then add several integers to the tree and finally print out the height of the tree. If I add integers of 10, 15 and 2 the tree should have a height of 2 i.e. 10 at the root, 15 to the right of 10 and 2 to the left of 10. Although the height is printed out as 3. Can anyone tell me what I am doing wrong please?

TreeNode.cpp

  #include "TreeNode.h"


TreeNode::TreeNode(int theData)
{
	theData = value;
}

BinaryTree.cpp

#include "BinaryTree.h"
#include "TreeNode.h"

BinaryTree::BinaryTree()
{
	rootPtr = NULL;
}

void BinaryTree::add(int data)
{
	if (rootPtr != NULL) {
		add(rootPtr, data);
	}
	else {
		rootPtr = new TreeNode(data);
		rootPtr->left = NULL;
		rootPtr->right = NULL;
	}
}

void BinaryTree::add(TreeNode* toAdd, int data)
{
	if (data < toAdd->value) {
		if (toAdd->left != NULL) {
			add(toAdd->left, data);
		}
		else {
			toAdd->left = new TreeNode(data);
			toAdd->left->left = NULL;
			toAdd->left->right = NULL;
		}
	}
	else {
		if (toAdd->right != NULL) {
			add(toAdd->right, data);
		}
		else {
			toAdd->right = new TreeNode(data);
			toAdd->right->left = NULL;
			toAdd->right->right = NULL;
		}
	}

}

int BinaryTree::height()
{
	return height(rootPtr);
}

int BinaryTree::height(TreeNode* node)
{
	if (node == NULL) {
		return 0;
	}
	else {
		int leftSide = height(node->left);
		int rightSide = height(node->right);
		
		if (leftSide > rightSide)
			return(leftSide + 1);
		else return (rightSide + 1);

		
	}

}

Main.cpp

#include "BinaryTree.h"
#include <iostream>
using namespace std;

int main()
{
	BinaryTree tree = BinaryTree();

	tree.add(10);
	tree.add(15);
	tree.add(2);

	cout << tree.height();


	return 0;
}

[lastchance]

Well, you haven't supplied the relevant .h files, but I can't see how this is right:

TreeNode::TreeNode(int theData)
{
	theData = value;
}

Maybe you meant

TreeNode::TreeNode(int theData)
{
	value = theData;
}

But difficult to say without the relevant code.

[darego]

I don't know how I managed to do that.. thanks a lot!

[dutch]

You haven't shown your header files, but your TreeNode ctor isn't initializing the left and right pointers to nullptr (don't use NULL!). Also, the assignment that you do have in that ctor looks backwards. Usually we would use the initializer list, anyway:

TreeNode::TreeNode(int theData)
    : value(theData), left(nullptr), right(nullptr)
{
}

[darego]

thanks dutch

[darego]

dutch, so you suggest i change all of the NULL values in my BinaryTree.cpp file to nullptr also?

[dutch]

Yes (unless you're compiling as pre-C++11, which you shouldn't!).

I'm not sure how simply reversing that assignment would affect the operation of height. (?)

Note that you can test for nulls with boolean operations, like so:

// instead of
if (ptr == nullptr) { }
// just say
if (!ptr) { }

// and instead of
if (ptr != nullptr) {}
// just say
if (ptr) {}

Also:

//You don't need to say
BinaryTree tree = BinaryTree();

// just say
BinaryTree tree;

I would also use spaces instead of tabs.

Here's the code in one file (with reconstructed headers). This way it can be run online by clicking the gear symbol beside the code.

// TreeNode.h ////////////////////////////////////////
struct TreeNode {
    int value;
    TreeNode *left, *right;
    TreeNode(int theValue);
};

// TreeNode.cpp ////////////////////////////////////////
//#include "TreeNode.h"

TreeNode::TreeNode(int theValue)
    : value(theValue), left(nullptr), right(nullptr) {
}

// BinaryTree.h ////////////////////////////////////////
class BinaryTree {
    TreeNode *rootPtr;

    static void add(TreeNode* toAdd, int data);
    static int height(TreeNode* node);

public:
    BinaryTree();
    void add(int data);
    int height();
};

// BinaryTree.cpp ////////////////////////////////////////
//#include "BinaryTree.h"
//#include "TreeNode.h"

BinaryTree::BinaryTree()
    : rootPtr(nullptr) {
}

void BinaryTree::add(int data) {
    if (rootPtr)
        add(rootPtr, data);
    else
        rootPtr = new TreeNode(data);
}

void BinaryTree::add(TreeNode* toAdd, int data) {
    if (data < toAdd->value)
        if (toAdd->left)
            add(toAdd->left, data);
        else
            toAdd->left = new TreeNode(data);
    else
        if (toAdd->right)
            add(toAdd->right, data);
        else
            toAdd->right = new TreeNode(data);
}

int BinaryTree::height() {
    return height(rootPtr);
}

int BinaryTree::height(TreeNode* node) {
    if (!node) return 0;
    int leftSide  = height(node->left);
    int rightSide = height(node->right);
    return (leftSide > rightSide ? leftSide : rightSide) + 1;
}

// main.cpp ////////////////////////////////////////
//#include "BinaryTree.h"
#include <iostream>

int main()
{
    BinaryTree tree;

    for (int n: {10, 15, 2})
        tree.add(n);

    std::cout << tree.height() << '\n';
}

[darego]

fantastic, thanks a lot for that!

[dutch]

me wrote:

I'm not sure how simply reversing that assignment would affect the operation of height. (?)

I figured it out. If all the uninitialized values end up being 0 (which is very possible since the OS zeroes new pages that it allocates to a process) then the tree will be created in a "straight line" (basically a linked list) and will therefore have a height equal to its node count.

[darego]

makes sense! I could really not figure out why the height was incrementing linearly as i added nodes. thanks again for the help