Binary Search Trees

[Skynet]

So I have this code that I wrote that pretty much makes a binary search tree with one node per element that holds the data int, one pointer for left, and one pointer for right. My tree is set that if you give it a number it starts as root, then afterwards any number you give it will either be placed left or right if it smaller than the current node or bigger respectively until it hits a pointer that points to NULL.

I was able to get my code to display the numbers in order no matter how bad you inserted the numbers to throw me off. My question now is this, how can I make it count how many levels there are? I'm not sure if this is clear or unclear but I want it to take all the paths and return to me the longest path and that should be how many levels there are. Any ideas how I can do this? Thank you.

#include <iostream>
using namespace std;

class binarySearchTree
{
private:
	class node
	{
	public:
		int data;
		node * left;
		node * right;

		node(int x)
		{
			data = x;
			left = NULL;
			right = NULL;
		}
	};

	node * root;

	//recursive methods

	void recInsert(int x, node * &r)
	{
		if( r == NULL )
		{
			r = new node(x);
		}
		else
		{
			if( x < r->data )
			{
				recInsert(x, r->left);
			}
			else
			{
				recInsert(x, r->right);
			}
		}
	}

	//display items in tree rooted at r
	void recDisplay(node * r)
	{
		if( r != NULL )
		{
			recDisplay(r->left);
			cout << r->data << endl;		
			recDisplay(r->right);
		}
	}

	//return height of tree rooted at r
	int getHeight( node * r )
	{

	}

public:

	binarySearchTree()
	{
		root = NULL;
	}

	void insert(int x)
	{
		recInsert(x, root);
	}

	//display all items in tree
	void display()
	{
		recDisplay(root);
	}


};

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

int main()
{

	binarySearchTree tree;

	tree.insert(53);
	tree.insert(11);
	tree.insert(7);
	tree.insert(5);
	tree.insert(2);
	tree.insert(23);

	tree.display();

	return 0;
}

[theranga]

The best I can think of is a recursive function that tests every path, something like this:

int getHeight (node * r)
{
// Max is the greatest height below (*r), temp is just used to avoid calling getHeight(r->right) twice
    int max=0,temp=0;
// Recurse down lhs
    if (r->left!=NULL) max=getHeight(r->left);
// Recurse down rhs
    if (r->right!=NULL) temp=getHeight(r->right);
    if (temp>max) max=temp;

// Return 1 more than max
    return max+1;
}

This is always linear complexity

[Skynet]

I tried taking a good hard look at it and it seems to me that it will always return an erroneous number cause doesn't max and temp get reset everytime you call it producing a 1 or 2 everytime? I'm not sure, right now I'm currently tired. Correct me if I'm wrong, which I probably am. lol

[randisking]

instead, write it something like this:

int getHeight (node * r)
{
   if( r == null)
   {
      return(0);
   }

   else
   {
      leftHeight = getHeight(r->left);
      rightHeight = getHeight(r->right);

      if(leftHeight > rightHeight)
      {
         return(leftHeight + 1);
      }
      else
      {
         return(rightHeight + 1);
      }
   }
}

[theranga]

@randisking
Your function is probably better because it's more clear - mine is like it only optimised

[randisking]

@theranga the problem is max and temp are getting reinitialized each recursion. I believe Skynet is correct, it's not likely going to produce a correct result because of that.

[theranga]

it will work.

my algorithm pretty obviously does exactly the same thing as yours, so that bit's fine.

max and temp are local to that particular instance of the function, so they are not reinitialised every recursion. If they were global variables, that would be a problem, but they aren't, so there isn't an issue.