Re:height of a BST by iteration - kindly review my solution
- From: "subramanian100in@xxxxxxxxx, India" <subramanian100in@xxxxxxxxx>
- Date: 29 Mar 2007 04:49:02 -0700
In the previous post, I had requested the experts to fix the bug.
Now, I have managed to fix the bug with some work-around.
I have given below the structures and the function that finds the tree
height.
I have tested the function for several input sets and it is working.
Kindly review the code and suggest me improvements. Please tell me if
there is an easier way of finding the height of a BST by iteration.
Thanks
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 treeHeightList
{
TreeNode *node;
bool toBeDeleted;
struct treeHeightList *next;
};
typedef struct treeHeightList TreeHeightList;
bool getTreeHeightByPreOrderIteration(
BST *tree,
unsigned int *treeHeight)
{
*treeHeight = 0;
TreeHeightList *list = NULL;
TreeHeightList *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)
{
deleteTreeHeightList(list);
list = NULL;
return false;
}
tmp->node = node;
tmp->toBeDeleted = false;
tmp->next = list;
list = tmp;
node = node->left;
}
if (list != NULL)
{
tmp = list;
if (tmp->toBeDeleted == false)
{
node = tmp->node;
if (node->right != NULL)
{
tmp->toBeDeleted = true;
node = node->right;
}
else
{
list = list->next;
free(tmp);
tmp = NULL;
node = NULL;
--curHeight;
}
}
else
{
list = list->next;
free(tmp);
tmp = NULL;
--curHeight;
}
}
else
break;
}
// here list will be NULL. So
// deleteTreeHeightList shall not be invoked.
return true;
}
Thanks
.
- References:
- finding height of a BST by iteration
- From: subramanian100in@xxxxxxxxx, India
- Re: finding height of a BST by iteration
- From: CBFalconer
- Re: finding height of a BST by iteration
- From: subramanian100in@xxxxxxxxx, India
- Re: finding height of a BST by iteration
- From: subramanian100in@xxxxxxxxx, India
- finding height of a BST by iteration
- Prev by Date: Re: bison and valgrind
- Next by Date: Re: bison and valgrind
- Previous by thread: Re: finding height of a BST by iteration
- Next by thread: correctness of physics function
- Index(es):