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
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