Binary tree traversal C++ implementation – stack with Morris

Pre-order, mid-order, post-order traversal

Leetcode 94. Middle order traversal of binary trees

Stack iteration

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(! root)return {};
        stack<TreeNode*> st;
        vector<int> ans;
        st.push(root);
        while(! st.empty())
        {
            TreeNode* current = st.top(a); st.pop(a); ans.push_back(current->val);
            if (current->right)st.push(current->right);
            if (current->left)st.push(current->left);
        }
        return ans;
    }

    vector<int> inorderTraversal(TreeNode* root) {
        if(! root)return {};
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* current = root;
        st.push(current);
        while(! st.empty())
        {
            while (current && current->left)
            {
                st.push(current->left);
                current = current->left;
            }
            current = st.top(a); st.pop(a); ans.push_back(current->val);
            if (current->right)
            {
                st.push(current->right);
                current = current->right;
            }
            else current = NULL;
        }
        return ans;
    }

    vector<int> postorderTraversal(TreeNode* root) {
        if(! root)return {};
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* current = root,*pre=NULL;
        st.push(current);
        while(! st.empty())
        {
            while (current && current->left)
            {
                st.push(current->left);
                current = current->left;
            }
            while(! st.empty())
            {
                current = st.top(a);if(pre==current->right || ! current->right) { st.pop(a); ans.push_back(current->val);
                    pre = current;
                }
                else
                {
                    st.push(current->right);
                    current = current->right;
                    break; }}}returnans; }};int main(a)
{
    /* Test case 1 / \ 23 / \ / \ 4 5 6 7 / \ 8 9 */
    Solution sol;
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->left->left->left = new TreeNode(8);
    root->right->left->right = new TreeNode(9);
    vector<int> ans = sol.preorderTraversal(root);
    cout <<endl<< "---preorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    ans = sol.inorderTraversal(root);
    cout << endl << "---inorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    ans=sol.postorderTraversal(root);
    cout << endl << "---postorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    cout << endl;
    return 0;
}
Copy the code

The output

---preorderTraversal---
1 2 4 8 5 3 6 9 7
---inorderTraversal---
8 4 2 5 1 6 9 3 7
---postorderTraversal---
8 4 5 2 9 6 7 3 1
Copy the code

Morris traversal

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

// Morris Traversal
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(! root)return {};
        vector<int> ans;
        TreeNode* head = root;
        TreeNode* current;
        while (head)
        {
            current = head->left;
            if (current)
            {
                while(current->right && current->right ! = head) { current = current->right; }if(! current->right) { current->right = head; ans.push_back(head->val);
                    head = head->left;
                    continue;
                }
                else // current->right == head
                { 
                    current->right = NULL; }}else
            {
                ans.push_back(head->val);
            }
            head = head->right;
        }
        return ans;
    }
   
    vector<int> inorderTraversal(TreeNode* root) {
        if(! root)return {};
        vector<int> ans;
        TreeNode* head = root;
        TreeNode* current;
        while (head)
        {
            current = head->left;
            if (current)
            {
                while(current->right && current->right ! = head) { current = current->right; }if(! current->right) { current->right = head; head = head->left;continue;
                }
                else // current->right == head
                {
                    current->right = NULL;
                }
            }
            ans.push_back(head->val);
            head = head->right;
        }
        return ans;
    }

    vector<int> postorderTraversal(TreeNode* root) {
        if(! root)return {};
        vector<int> ans;
        TreeNode* head = root;
        TreeNode* current;
        while (head)
        {
            current = head->left;
            if (current)
            {
                while(current->right && current->right ! = head) { current = current->right; }if(! current->right) { current->right = head; head = head->left;continue;
                }
                else // current->right == head
                {
                    current->right = NULL;
                    stack<TreeNode*> st;
                    st.push(head->left);
                    while (st.top()->right)
                    {
                        st.push(st.top()->right);
                    }
                    while(! st.empty())
                    {
                        ans.push_back(st.top()->val);
                        st.pop(a); } } } head = head->right; } stack<TreeNode*> st; st.push(root);
        while (st.top()->right)
        {
            st.push(st.top()->right);
        }
        while(! st.empty())
        {
            ans.push_back(st.top()->val);
            st.pop(a); }returnans; }};int main(a)
{
    /* Test case 1 / \ 23 / \ / \ 4 5 6 7 / \ 8 9 */
    Solution sol;
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->left->left->left = new TreeNode(8);
    root->right->left->right = new TreeNode(9);
    vector<int> ans = sol.preorderTraversal(root);
    cout << endl << "---preorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    ans = sol.inorderTraversal(root);
    cout << endl << "---inorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    ans = sol.postorderTraversal(root);
    cout << endl << "---postorderTraversal---" << endl;
    for (auto a : ans)cout << a << "";
    cout << endl;
    return 0;
}

Copy the code

Threaded Binary Tree ans Morris traversal

Inorder Tree Traversal without Recursion

Inorder Tree Traversal without Recursion

// C++ program to print inorder traversal 
// using stack. 
#include<iostream>
#include<stack>
using namespace std;

/* A binary tree Node has data, pointer to left child
and a pointer to right child */
struct Node
{
	int data;
	struct Node* left;
	struct Node* right;
	Node(int data)
	{
		this->data = data;
		left = right = NULL; }};/* Iterative function for inorder tree
traversal */
void inOrder(struct Node* root)
{
	stack<Node*> s;
	Node* curr = root;

	while(curr ! =NULL || s.empty() = =false)
	{
		/* Reach the left most Node of the curr Node */
		while(curr ! =NULL)
		{
			/* place pointer to a tree node on the stack before traversing the node's left subtree */
			s.push(curr);
			curr = curr->left;
		}

		/* Current must be NULL at this point */
		curr = s.top(a); s.pop(a); cout << curr->data <<"";

		/* we have visited the node and its left subtree. Now, it's right subtree's turn */
		curr = curr->right;

	} /* end of while */
}

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

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

	inOrder(root);
	return 0;
}
Copy the code