Re: finding height of a BST by iteration

On Mar 28, 11:22 am, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
"subramanian10...@xxxxxxxxx, India" <subramanian10...@xxxxxxxxx>
writes:

I know the Inorder, Preorder and Postorder traversal of a BST by
iteration.
Still I do not know how to calculate the height of a BST by iteration.

Traverse the BST. Each time you move downward, increment a
counter; if the counter is greater than the maximum known height,
then set the maximum known height to the counter. Each time you
move upward, decrement the counter. When traversal is finished,
the maximum known height is the height.
--
Ben Pfaffhttp://benpfaff.org

I tried to implement your loigc. But I could not code it correctly.
Following is the function.

struct binaryTreeNode
{
int value;
struct binaryTreeNode *left;
struct binaryTreeNode *right;
};

typedef struct binaryTreeNode TreeNode;

struct binaryTree
{
TreeNode *root;
unsigned int nodeCount;
void (*processNode)(TreeNode *node);
};

typedef struct binaryTree BST;

struct binaryTreeList
{
TreeNode *node;
struct binaryTreeList *next;
};

typedef struct binaryTreeList TreeList;

bool getTreeHeight(BST *tree, unsigned int *treeHeight)
{
*treeHeight = 0;

TreeList *list = NULL;
TreeList *tmp;
unsigned int curHeight = 0;

for (TreeNode *node = tree->root; ;)
{
while (node != NULL)
{
++curHeight;
if (*treeHeight < curHeight)
*treeHeight = curHeight;

tmp = malloc(sizeof *tmp);
if (tmp == NULL)
{
deleteList(list);
list = NULL;
return false;
}

tmp->node = node;
tmp->next = list;
list = tmp;

node = node->left;
}

if (list != NULL)
{
tmp = list;
list = list->next;
node = tmp->node;
free(tmp);
tmp = NULL;

node = node->right;

if (node == NULL)
--curHeight;
}
else
break;
}

// here list will be NULL.
// So deleteList shall not be invoked.

return true;
}

Sample Input:
38 14 8 23 18 20 56 45 82 70 75

For this input, tree height is printed as 7.

I could not fix the bug in the code. Kindly help me.

Thanks

.