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