binarytree.cpp

#include <iostream>
#include <memory>
#include <stack>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
    Node(int data) : data(data), left(nullptr), right(nullptr) {}

    int data;
    std::unique_ptr<Node> left, right;
};

// print its nodes according to the "bottom-up" postorder traversal.
void printPostorder(Node* node)
{
	if (node == nullptr)
		return;

	// first recur on left subtree
	printPostorder(node->left.get());

	// then recur on right subtree
	printPostorder(node->right.get());

	// now deal with the node
	std::cout <<  node->data << ' ';
}

// print its nodes in inorder
void printInorder(Node* node)
{
	if (node == nullptr)
		return;

	// first recur on left child 
	printInorder(node->left.get());

	// then print the data of node
	std::cout << node->data << ' '; 

	// now recur on right child
	printInorder(node->right.get());
}

// print its nodes in preorder
void printPreorder(Node* node)
{
	if (node == nullptr)
		return;

	// first print data of node
	std::cout << node->data << ' '; 

	// then recur on left sutree
	printPreorder(node->left.get()); 

	// now recur on right subtree
	printPreorder(node->right.get());
} 
// print its nodes according to the "bottom-up" postorder traversal.
void printPostorderWithoutRecur(Node* node)
{
  	if (node == nullptr) return;
    
    std::stack<Node*> nodeStack; // for traversal
    std::stack<Node*> output; // to print
    
    nodeStack.push(node);
    
    while (!nodeStack.empty()) {
        auto current = nodeStack.top(); nodeStack.pop();
        output.push(current);
        if (current->left)
            nodeStack.push(current->left.get());
        if (current->right)
            nodeStack.push(current->right.get());
    }
    while (!output.empty()) {
        std::cout << output.top()->data << " ";
        output.pop();
    }
}

// print its nodes in inorder
void printInorderWithoutRecur(Node* node)
{
	if (node == nullptr)
		return;

    std::stack<Node*> nodeStack;
    auto current = node;
    
    while (!nodeStack.empty() || current) {
        if (current) {
            nodeStack.push(current);
            current = current->left.get();
        } else {
            current = nodeStack.top(); nodeStack.pop();
            std::cout << current->data << " ";
            current = current->right.get();
        }
    }
}

// print its nodes in preorder
void printPreorderWithoutRecur(Node* node)
{
	if (node == nullptr)
		return;
 
    std::stack<Node*> nodeStack;
    nodeStack.push(node);
 
    while (!nodeStack.empty()) {
        auto current = nodeStack.top(); nodeStack.pop();
        std:: cout << current->data << ' ';
        if (current->right)
            nodeStack.push(current->right.get());
        if (current->left)
            nodeStack.push(current->left.get());
    }
} 

int main()
{
	auto root          = std::make_unique<Node>(1);
	root->left	       = std::make_unique<Node>(2);
	root->right		   = std::make_unique<Node>(3);
	root->left->left   = std::make_unique<Node>(4);
	root->left->right  = std::make_unique<Node>(5); 

	std::cout << "\nPreorder traversal of binary tree is \n";
	printPreorder(root.get());
    std::cout << "\nPreorder traversal of binary tree is (without recur) \n";
    printPreorderWithoutRecur(root.get());
    
	std::cout << "\n\nInorder traversal of binary tree is \n";
	printInorder(root.get()); 
    std::cout << "\nInorder traversal of binary tree is (without recur) \n";
    printInorderWithoutRecur(root.get());
    
	std::cout << "\n\nPostorder traversal of binary tree is \n";
	printPostorder(root.get()); 
    std::cout << "\nPostorder traversal of binary tree is (without recur) \n";
    printPostorderWithoutRecur(root.get());
}

binarytreee.cpp

#include <iostream>
#include <memory>
#include <stack>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
    int data = 0;
    Node *left = nullptr; 
    Node *right = nullptr;
};

// print its nodes according to the "bottom-up" postorder traversal.
void printPostorder(Node* node)
{
	if (node == nullptr)
		return;

	// first recur on left subtree
	printPostorder(node->left);

	// then recur on right subtree
	printPostorder(node->right);

	// now deal with the node
	std::cout <<  node->data << ' ';
}

// print its nodes in inorder
void printInorder(Node* node)
{
	if (node == nullptr)
		return;

	// first recur on left child 
	printInorder(node->left);

	// then print the data of node
	std::cout << node->data << ' '; 

	// now recur on right child
	printInorder(node->right);
}

// print its nodes in preorder
void printPreorder(Node* node)
{
	if (node == nullptr)
		return;

	// first print data of node
	std::cout << node->data << ' '; 

	// then recur on left sutree
	printPreorder(node->left); 

	// now recur on right subtree
	printPreorder(node->right);
} 
// print its nodes according to the "bottom-up" postorder traversal.
void printPostorderWithoutRecur(Node* node)
{
  	if (node == nullptr) return;
    
    std::stack<Node*> nodeStack; // for traversal
    std::stack<Node*> output; // to print
    
    nodeStack.push(node);
    
    while (!nodeStack.empty()) {
        auto current = nodeStack.top(); nodeStack.pop();
        output.push(current);
        if (current->left)
            nodeStack.push(current->left);
        if (current->right)
            nodeStack.push(current->right);
    }
    while (!output.empty()) {
        std::cout << output.top()->data << " ";
        output.pop();
    }
}

// print its nodes in inorder
void printInorderWithoutRecur(Node* node)
{
	if (node == nullptr)
		return;

    std::stack<Node*> nodeStack;
    auto current = node;
    
    while (!nodeStack.empty() || current) {
        if (current) {
            nodeStack.push(current);
            current = current->left;
        } else {
            current = nodeStack.top(); nodeStack.pop();
            std::cout << current->data << " ";
            current = current->right;
        }
    }
}

// print its nodes in preorder
void printPreorderWithoutRecur(Node* node)
{
	if (node == nullptr)
		return;
 
    std::stack<Node*> nodeStack;
    nodeStack.push(node);
 
    while (!nodeStack.empty()) {
        auto current = nodeStack.top(); nodeStack.pop();
        std:: cout << current->data << ' ';
        if (current->right)
            nodeStack.push(current->right);
        if (current->left)
            nodeStack.push(current->left);
    }
} 

int main()
{
    // create 5 nodes
	Node root, node1, node2, node3,node4;
    // give them some value
    root.data = 1; 
    node1.data = 2;
    node2.data = 3;
    node3.data = 4;
    node4.data = 5;
    // link them to complete binary tree structure
	root.left = &node1;
	root.right = &node2;
	root.left->left = &node3;
	root.left->right = &node4; 

	std::cout << "\nPreorder traversal of binary tree is \n";
	printPreorder(&root);
    std::cout << "\nPreorder traversal of binary tree is (without recur) \n";
    printPreorderWithoutRecur(&root);
    
	std::cout << "\n\nInorder traversal of binary tree is \n";
	printInorder(&root); 
    std::cout << "\nInorder traversal of binary tree is (without recur) \n";
    printInorderWithoutRecur(&root);
    
	std::cout << "\n\nPostorder traversal of binary tree is \n";
	printPostorder(&root); 
    std::cout << "\nPostorder traversal of binary tree is (without recur) \n";
    printPostorderWithoutRecur(&root);
}