Lecture 278:- Binary Tree Traversal Easy Method 3

Another easy method to perform binary tree traversal is using Morris Traversal. Morris Traversal is an efficient method that does not require additional data structures like stacks or queues. It allows us to traverse the binary tree in both inorder and preorder without using recursion or extra space.

Here's a simple implementation of Morris Traversal for both inorder and preorder traversals in C++:

cppCopy code

#include <iostream> struct Node {    int data;    Node* left;    Node* right;    Node(int val) {        data = val;        left = nullptr;        right = nullptr;    } }; // Inorder Traversal using Morris Traversal void inorderTraversal(Node* root) {    Node* curr = root;    while (curr) {        if (!curr->left) {            std::cout << curr->data << " ";            curr = curr->right;        } else {            Node* predecessor = curr->left;            while (predecessor->right && predecessor->right != curr)                predecessor = predecessor->right;            if (!predecessor->right) {                predecessor->right = curr;                curr = curr->left;            } else {                predecessor->right = nullptr;                std::cout << curr->data << " ";                curr = curr->right;            }        }    } } // Preorder Traversal using Morris Traversal void preorderTraversal(Node* root) {    Node* curr = root;    while (curr) {        if (!curr->left) {            std::cout << curr->data << " ";            curr = curr->right;        } else {            Node* predecessor = curr->left;            while (predecessor->right && predecessor->right != curr)                predecessor = predecessor->right;            if (!predecessor->right) {                std::cout << curr->data << " ";                predecessor->right = curr;                curr = curr->left;            } else {                predecessor->right = nullptr;                curr = curr->right;            }        }    } } int main() {    // Create a binary tree:    //        1    //       / \    //      2   3    //     / \    //    4   5    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);    // Perform different traversals    std::cout << "Inorder Traversal: ";    inorderTraversal(root);    std::cout << std::endl;    std::cout << "Preorder Traversal: ";    preorderTraversal(root);    std::cout << std::endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right;    delete root;    return 0; }

In Morris Traversal, we modify the binary tree structure temporarily without using extra space. The traversal follows the left pointers to the leftmost node and then backtracks to the original node after processing. The Morris Traversal is an efficient approach that enables us to perform both inorder and preorder traversals in O(1) space complexity and without using recursion.