Skip to main content

Inorder traversal of binary tree using stack in c

C program for Inorder traversal of binary tree using stack. Here problem description and explanation.

/*
  C Program 
  Inorder Tree Traversal of a Binary Tree
  Using Stack
*/
#include <stdio.h>
#include <stdlib.h>
// Binary Tree node
struct TreeNode
{
    int data;
    struct TreeNode *left, *right;
};
// Binary Tree
struct BinaryTree
{
    struct TreeNode *root;
};
// Stack Node
struct StackNode
{
    struct TreeNode *element;
    struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
    struct StackNode *top;
    int size;
};
struct MyStack *newStack()
{
    // Make a stack
    struct MyStack *stack = 
      (struct MyStack *) malloc(sizeof(struct MyStack));
    if (stack != NULL)
    {
        // Set node values
        stack->top = NULL;
        stack->size = 0;
    }
    else
    {
        printf("\nMemory overflow when create new stack\n");
    }
    return stack;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
    if (stack->size > 0 && stack->top != NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
// Add node at the top of stack
void push(struct MyStack *stack, struct TreeNode *element)
{
    // Make a new node
    struct StackNode *node = 
      (struct StackNode *) malloc(sizeof(struct StackNode));
    if (node == NULL)
    {
        printf("\nMemory overflow when create new stack Node \n");
    }
    else
    {
        node->element = element;
        node->next = stack->top;
    }
    // Add stack element
    stack->top = node;
    stack->size++;
}
// Return top element of stack
struct TreeNode *peek(struct MyStack *stack)
{
    if (stack == NULL)
    {
        return NULL;
    }
    return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
    if (!isEmpty(stack))
    {
        struct StackNode *temp = stack->top;
        // Change top element of stack
        stack->top = temp->next;
        // remove previous top
        free(temp);
        temp = NULL;
        stack->size--;
    }
}
// Create new tree
struct BinaryTree *newTree()
{
    // Create dynamic node
    struct BinaryTree *tree = 
      (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    // Return new tree
    return tree;
}
// This is creating a binary tree node and return this
struct TreeNode *getNode(int data)
{
    // Create dynamic node
    struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        // Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        // This is indicates, segmentation fault or 
        // Memory overflow problem
        printf("Memory Overflow\n");
    }
    // Return new node
    return node;
}
// Display Inorder view of binary tree
void inorder(struct TreeNode *root)
{
    if (root != NULL)
    {
        // Make new stack 
        struct MyStack *s = newStack();
        struct TreeNode *node = root;
        // Display tree element
        while (!isEmpty(s) || node != NULL)
        {
            if (node != NULL)
            {
                // Add current node
                push(s, node);
                // Visit to left subtree
                node = node->left;
            }
            else
            {
                // When node is null
                // Get stack top element
                node = peek(s);
                // Display node value
                printf("%d  ", node->data);
                // Remove top element of the stack
                pop(s);
                // Visit to left subtree of current node
                node = node->right;
            }
        }
    }
    else
    {
        printf("Empty Linked List\n");
    }
}
int main()
{
    struct BinaryTree *tree = newTree();
    /*
        Create Binary Tree
        -------------------
            15
           /  \
          24   54
         /    /  \
        35   62   13
    */
    // Add tree node
    tree->root = getNode(15);
    tree->root->left = getNode(24);
    tree->root->right = getNode(54);
    tree->root->right->right = getNode(13);
    tree->root->right->left = getNode(62);
    tree->root->left->left = getNode(35);
    // Display Tree elements
    inorder(tree->root);
    return 0;
}

Output

35  24  15  62  54  13




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment