Problem Statement

Given root of binary tree, return the preorder traversal of the binary tree.

Morris preorder Traversal is a tree traversal algorithm aiming to achieve a space complexity of O(1) without recursion or an external data structure.

Examples

Example 1:

Input: root = [1, 4, null, 4, 2]
Output: [1, 4, 4, 2]

Different Approaches

1️⃣ Threading

Intuition:

To address this problem, it is crucial to understand the Morris Inorder Traversal technique for binary trees. Morris Inorder Traversal, known for its space efficiency, can be adapted to perform Preorder Traversal by modifying the traversal method. Specifically, in Preorder Morris Traversal, the value of the current node is printed before proceeding to its left child, but only if the right child of the inorder predecessor is null.

This modification maintains the core structure of Morris Traversal while ensuring that nodes are processed in the sequence required for Preorder Traversal. As a result, the traversal remains efficient, operating in constant space, as it does not require additional data structures.

Approach:

1. Begin by initializing a pointer, current, to traverse the tree, and set it to the root node of the binary tree.
2. Perform the traversal while current is not null:
   1. If the current node does not have a left child, print the value of the current node and move to its right child.
   2. If the current node has a left child:
   3. Identify the inorder predecessor of the current node, which is the rightmost node in the left subtree.
   4. If the right child of this inorder predecessor is null, establish a temporary link by setting the right child of the inorder predecessor to the current node. Print the value of the current node and move to its left child.
   5. If the right child of the inorder predecessor is not null, this indicates that the temporary link established earlier has been encountered. Therefore, revert the changes by setting the right child of the inorder predecessor back to null and proceed to the current node’s right child.
3. Continue this process until the traversal reaches the end of the binary tree.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> preorder(TreeNode* root) {
        // Vector to store the preorder traversal result
        vector<int> preorder;
        // Pointer to the current node, starting with the root
        TreeNode* cur = root;

        /* 
        Iterate until the current node becomes null
        If the current node has no left child
        Add the value of the current node to the preorder list
        */
        while (cur != NULL) {
            if (cur->left == NULL) {
                preorder.push_back(cur->data);
                cur = cur->right;
            } 
        /* 
        If the current node has a left child create a pointer 
        to traverse to the rightmost node in the left subtree
        or until we find a node whose right child is not yet processed
        */     
            else {
                TreeNode* prev = cur->left;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }
        /* 
        If the right child of the rightmost node is null 
        set the right child of the rightmost node to the current node
        Add the value of the current node to the preorder list
        and move to the left child
        */        

                if (prev->right == NULL) {
                    prev->right = cur;
                    preorder.push_back(cur->data);
                    cur = cur->left;
                } 

        /* If the right child of the rightmost node is not null
        Reset the right child to null and move to the right child */ 

                else {
                    prev->right = NULL;
                    cur = cur->right;
                }
            }
        }
        // Return the resulting preorder traversal list
        return preorder;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(4);
    root->left->left->left = new TreeNode(2);

    Solution sol;
    vector<int> preorder = sol.preorder(root);

    cout << "Binary Tree Morris Preorder Traversal: ";
    for (int i : preorder) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(2N) where N is the number of nodes in the Binary Tree. The algorithm visits each node at most twice.
• Space Complexity:O(1) The algorithm uses constant extra space for auxiliary variables.