Inorder traversal of binary tree using stack in c++
C++ program for Inorder traversal of binary tree using stack. Here problem description and explanation.
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Inorder traversal without recursion
// Using stack
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
// Make a tree node
TreeNode(int data)
{
// Set node data
this->data = data;
this->left = nullptr;
this->right = nullptr;
}
};
class StackNode
{
public: TreeNode *element;
StackNode *next;
StackNode(TreeNode *element)
{
this->element = element;
this->next = nullptr;
}
};
// Stack Class
class MyStack
{
public:
StackNode *top;
int size;
MyStack()
{
this->top = nullptr;
this->size = 0;
}
// Add new element into stack
void push(TreeNode *element)
{
// Create new node
StackNode *node = new StackNode(element);
node->next = this->top;
// new node is new top
this->top = node;
// Increase the size
this->size += 1;
}
// Remove top element of the stack
void pop()
{
if (this->top != nullptr)
{
// next node is new top
this->top = this->top->next;
// Reduce size
this->size -= 1;
}
}
// Returns the status of empty or non empty stacks
bool isEmpty()
{
if (this->size > 0 && this->top != nullptr)
{
return false;
}
else
{
return true;
}
}
// Return top element of stack
TreeNode *peek()
{
if (this->isEmpty())
{
return nullptr;
}
return this->top->element;
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = nullptr;
}
// Display Inorder view of binary tree
void inorder()
{
if (this->root != nullptr)
{
// Make new stack
MyStack *s = new MyStack();
TreeNode *node = this->root;
// Display tree element
while (!s->isEmpty() || node != nullptr)
{
if (node != nullptr)
{
// Add current node
s->push(node);
// Visit to left subtree
node = node->left;
}
else
{
// When node is null
// Get stack top element
node = s->peek();
// Display node value
cout << " " << node->data;
// Remove top element of the stack
s->pop();
// Visit to left subtree of current node
node = node->right;
}
}
}
else
{
cout << "Empty Linked List\n";
}
}
};
int main()
{
// Create new tree
BinaryTree *tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
15
/ \
24 54
/ / \
35 62 13
*/
// Add tree nodes
tree->root = new TreeNode(15);
tree->root->left = new TreeNode(24);
tree->root->right = new TreeNode(54);
tree->root->right->right = new TreeNode(13);
tree->root->right->left = new TreeNode(62);
tree->root->left->left = new TreeNode(35);
// Display result
tree->inorder();
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