height of a BST by iteration - kindly review my solution

S

subramanian100in

I have given below the structures and the function that finds the
height of a BST by iteration.

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

Forum statistics

Threads
473,774
Messages
2,569,596
Members
45,128
Latest member
ElwoodPhil
Top