Member Avatar for aaronmk2

I an trying to find the height in a binary search tree. I figured out how to count the leaves going directly left and directly right, but cannot figure out how to get he leaves in the middle.

int BST::height(){
	int tall =0;
	int tall1=0;
	BinNodePtr ptr=myRoot;
	if (ptr->left =='\0' && ptr->right =='\0') 
		return tall;//up to this part I know is correct.
	else {
		while (ptr->left) {
			ptr=ptr->left;
			tall++;
		}
		ptr=myRoot;
		while (ptr->right) {
			ptr=ptr->right;
			tall1++;
		}
	}
	if (tall>tall1)
	return tall;
	else 
		return tall1;
  • 3 Contributors
  • 2 Replies
  • 264 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by mrnutty

Dani AI

Generated

Counting only the leftmost and rightmost chains will miss the true longest path when the deepest branch sits "in the middle." The first step is to pick a clear definition of height and stick with it: either (A) number of nodes on the longest root→leaf path (leaf height = 1, empty tree = 0), or (B) number of edges (leaf = 0, empty = -1). Variable names that reflect that choice make the code easier to read, as suggested.

There are a few concrete problems in the posted code from : comparing child pointers to the character literal '\0' is incorrect — use nullptr (or NULL in pre-C++11) and check the tree for an empty root. Walking only ptr->left and ptr->right finds only those extreme branches and so will give wrong results for many trees.

Recursion is the simplest and most direct approach (as recommended), but watch off-by-one errors. One correct node-counting recursive form is:

int height(Node* node) {
    if (node == nullptr) return 0;           // empty tree => 0
    int lh = height(node->left);
    int rh = height(node->right);
    return 1 + std::max(lh, rh);             // count this node
}

A non-recursive alternative uses level-order traversal to count levels (useful to avoid deep recursion on skewed trees):

int heightIterative(Node* root) {
    if (!root) return 0;
    std::queue<Node*> q;
    q.push(root);
    int h = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            Node* n = q.front(); q.pop();
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        ++h;
    }
    return h;
}

Notes: pick node- or edge-based semantics and document it; subtract 1 from these results if edges-based height is required. Also prefer nullptr, use descriptive names, and handle an empty myRoot explicitly.

Recommended Answers

All 2 Replies

Member Avatar for daviddoria

I think descriptive variable names and comments would be helpful here (and everywhere... :) )

I'm assuming 'tall' is the height? If so, name it 'height' and change the name of the function to GetHeight() or something like that. What is 'tall1'?

Add a comment to at least every conditional and every loop and I bet it will be come clear to you what is going on/wrong.

David

Member Avatar for mrnutty

For Binary search trees or any data structures that are recursive in nature,
you will want to implement a recursive algorithm to solve most of its problems.Its not only easier to write, but its easier to understand as well. So with that said, consider this recursive algorithm that finds the height of a tree.

int BinaryTree:height(){
 return _height(this.root);
}
int BinaryTree::_height(const Node* root){
  if( isNull( root) ) return 0;
  int leftTreeMax = _height(root.getLeft()) + 1; //add one and move down
  int rightTreeMax = _height(root.getRight()) + 1; //add one and move down
  return std::max(leftTreeMax, rightTreeMax) + 1; //account for the root
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.