finding the bst height

[liukevin]

i need some help on this...
i need to find the height of a BST with the function prototype

int height();

i know how to do it if the prototype is

int height (BSTNode *treePtr) const
{
if (treePtr == NULL)
return 0;
else
{
if (findheight (treePtr ->right) > findheight(treePtr ->left))
return 1 + findheight (treePtr ->right);
else
return 1 + findheight(treePtr ->left);
}
}

but with just int height()
i can't pass anything in there...

does anyone have any idea???

thanx

 

[ArkM]

What is it - BST? Binary Search Tree?
If so, is BST a class? If so, height() may be this class member function. If so, use it as:

BST bst;
...
bst.add(...); // or what else...
...
bst.height() // this is height of bst call...

Didn't you know that we are in C++ world?..

 

[liukevin]

ok .... allow me to explain.

BST = binary search tree

class BST
{
public:
.
.
int height()

private:
Node* root;

}

now i know how to use a class, calling it's function with a object.

but writing the code recursivly with no input parameter is the problem i'm having right now.

 

[ArkM]

Try this trick:

int Tree::height() // const
{
  if (!root)
     return 0;
  Node* p = root; // save current root pointer
  root = p->pleft;// root member as a temp var...
  int dleft = height();
  root = p->pright;
  int dright = height();
  root = p;
  return 1 + (dleft < dright? dright: dleft);// h(root) == 1
}

You must declare Tree as a friend of Node; or modify the code with Node left/right pointers accessors. If you declare height() const, add mutable modifier to root member declarator.

 

[PerFnurt]

Mutable root? IMHO, mutable should be done when it makes sense, not just as a clever const_cast.

>i need to find the height of a BST with the function prototype

>int height();

>i know how to do it if the prototype is

>int height (BSTNode *treePtr) const

Am I missing something obvious?

  int height() const { return height(theRoot); }
private:
  int height (BSTNode  *treePtr) const
  {
    ...
  }

/Per
[sub]
"It was a work of art, flawless, sublime. A triumph equaled only by its monumental failure."[/sub]

 

[ArkM]

1. What for const_cast here? I want to modify (temporarely) root member in const member function but I guarantee this tree object value consistence. It is exactly the case for mutable modifier.
2. It's an artificial situation (kind of game: height() without any arguments, without any helpers (in spirit of the original post)...
Here it is...

 

[PerFnurt]

>1. What for const_cast here?
Mutable does a permanent "const_cast" on root. It will never have const protection, not even where it should have.

Yes, its a temporary modification but it's done to the root, which I (and I admit - its just a gut feeling Ive got) consider is one of those members you actually want to protect from unintended modification.

>2. It's an artificial situation
I should hope so

/Per
[sub]
"It was a work of art, flawless, sublime. A triumph equaled only by its monumental failure."[/sub]

 

[ArkM]

About mutable root:
It's a private member (you see), so it's well protected from unintended modifications. Member functions make proper modifications only (by definition), mutables are invented exactly for that cases.

 

[PerFnurt]

>Member functions make proper modifications only (by definition)

If that was true then the whole "const method" mechanism would be totally pointless.

Which it isn't.


/Per
[sub]
"It was a work of art, flawless, sublime. A triumph equaled only by its monumental failure."[/sub]