Note 1

Take Note:

Take a note while surfing.





Note With Ink

Give your Note a Colorful Tag.




Easy to Access

Stay on same information and in Sync wherever you are.

Note 2

Take Note:

Organize your information,It may take Shape.





Think With Ink

Differ your Content by Color.




Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3

Take Note:

Don't Let information to miss,Because it take shape





Note With Ink

Simple an Easy Way to take a note.




Easy to Access

Get the same in next visit.

Program Discussion :: Trees
Home > Programs > Trees

49. Write a program to check whether the given tree is balanced or not

Answer:

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for 
stack. A stack node contains a pointer to tree node and a pointer to 
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;

while (!done)
{
    /* Reach the left most tNode of the current tNode */
    if(current != NULL)
    {
    /* place pointer to a tree node on the stack before traversing 
        the node's left subtree */
    push(&s, current);                                             
    current = current->left; 
    }
        
    /* backtrack from the empty subtree and visit the tNode 
    at the top of the stack; however, if the stack is empty,
    you are done */
    else                                                            
    {
    if (!isEmpty(s))
    {
        current = pop(&s);
        printf("%d ", current->data);

        /* we have visited the node and its left subtree.
        Now, it's right subtree's turn */
        current = current->right;
    }
    else
        done = 1; 
    }
} /* end of while */
}     

/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
    printf("Stack Overflow \n");
    getchar();
    exit(0);
}         

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref); 

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;


/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
    printf("Stack Underflow \n");
    getchar();
    exit(0);
}
else
{
    top = *top_ref;
    res = top->t;
    *top_ref = top->next;
    free(top);
    return res;
}
}

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
                    malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;

return(tNode);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
            1
        / \
        2     3
    / \
    4     5
*/
struct tNode *root = newtNode(1);
root->left     = newtNode(2);
root->right     = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5); 

inOrder(root);

getchar();
return 0;
}

Post Your Answer Here:

Name *
Email

Language:

Post Your Reply Here: