Morris Traversal in C++

Morris Traversal is a method for traversing binary trees without using any extra space for storing information about nodes. It allows for the traversal of a binary tree in Inorder, Preorder, and Postorder without recursion or using a stack.

Introduction

Morris Traversal is an elegant and efficient algorithm for traversing binary trees. It was introduced by J. H. Morris in 1979. The key idea behind Morris Traversal is to modify the tree as we traverse it so that we can navigate through the nodes without using any additional space for a stack or recursion. This method helps to reduce the space complexity of tree traversal algorithms.

Pseudo Code

The general idea behind Morris Traversal is as follows:

1. Initialize current as root
2. While current is not NULL
    a. If current does not have a left child
        i. Print current's data
        ii. Move to the right child (current = current->right)
    b. Else
        i. Find the inorder predecessor of current (say it's the rightmost node in current's left subtree, and cannot be current node)
        ii. If the right child of the predecessor is NULL
            1. Set the right child of the predecessor to current (Creating temp links)
            2. Move current to its left child (current = current->left)
        iii. Else
            1. Set the right child of the predecessor back to NULL (Removing temp links)
            2. Print current's data
            3. Move current to its right child (current = current->right)

Inorder Traversal using Morris Traversal

void morrisInorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

Preorder Traversal using Morris Traversal

void morrisPreorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                std::cout << current->data << " ";
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Postorder Traversal using Morris Traversal

void reverseNodes(Node* start, Node* end) {
    if (start == end) return;
    Node* x = start;
    Node* y = start->right;
    Node* z;
    while (x != end) {
        z = y->right;
        y->right = x;
        x = y;
        y = z;
    }
}

void printReverse(Node* start, Node* end) {
    reverseNodes(start, end);
    Node* current = end;
    while (true) {
        std::cout << current->data << " ";
        if (current == start) break;
        current = current->right;
    }
    reverseNodes(end, start);
}

void morrisPostorderTraversal(Node* root) {
    Node dummy;
    dummy.left = root;
    dummy.right = nullptr;
    Node* current = &dummy;
    while (current != nullptr) {
        if (current->left == nullptr) {
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                printReverse(current->left, predecessor);
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Main Driver Code

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Function prototypes
void morrisInorderTraversal(Node* root);
void morrisPreorderTraversal(Node* root);
void morrisPostorderTraversal(Node* root);

int main() {
    // Constructing a sample binary tree
    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);

    std::cout << "Inorder traversal: ";
    morrisInorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Preorder traversal: ";
    morrisPreorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Postorder traversal: ";
    morrisPostorderTraversal(root);
    std::cout << std::endl;

    // Deallocate memory
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

This main driver code constructs a binary tree, then applies each of the Morris Traversal methods (inorder, preorder, postorder) to print the traversals. Finally, it deallocates the memory allocated for the tree nodes.

Practice

• https://www.geeksforgeeks.org/problems/flatten-binary-tree-to-linked-list/1