Morris traversal for Preorder

Morris Traversal is a special method for traversing binary trees without using recursion or an explicit stack. It allows us to perform both in-order and pre-order traversals of a binary tree using only constant space while maintaining the original structure of the tree. The algorithm was introduced by J. H. Morris in 1979.

Problem Statement

Given a binary tree, we want to perform a pre-order traversal using the Morris Traversal technique. The goal is to print the values of the nodes in pre-order sequence.

Description

The Morris Traversal algorithm is based on the idea of threaded binary trees, where we temporarily modify the structure of the tree to create threads connecting some nodes. These threads help us traverse the tree without using a stack or recursion.

Let's understand the algorithm with an example:

Consider the binary tree:

      4
    /   \
   8     10
  / \   /  \
 1   6 7   -3
    /
   9

Idea to Solve the Problem

1. Start with the root node.
2. Initialize the current node as the root.
3. While the current node is not null: a. If the current node doesn't have a left child, print its value and move to the right child. b. If the current node has a left child: i. Find the rightmost node in the left subtree of the current node. ii. If the rightmost node doesn't have a threaded connection to the current node, establish a thread connection from it to the current node and print the current node's value. Move to the left child. iii. If a thread connection already exists, remove the thread connection and move to the right child.

Pseudocode

MorrisPreorder(root):
    current = root
    while current is not null:
        if current's left child is null:
            print current's value
            current = current's right child
        else:
            auxiliary = current's left child
            while auxiliary's right child is not null and auxiliary's right child is not current:
                auxiliary = auxiliary's right child
            if auxiliary's right child is null:
                print current's value
                auxiliary's right child = current
                current = current's left child
            else:
                auxiliary's right child = null
                current = current's right child

Algorithm Explanation

1. Start with the root node. Initialize current as the root node.
2. Traverse the tree using a while loop until current becomes null.

3. Inside the loop:

   a. If the current node doesn't have a left child, print its value and move to the right child.

   b. If the current node has a left child:

   i. Start with auxiliary as the left child of the current node.

   ii. Find the rightmost node in the left subtree by moving right until the right child of auxiliary

   is null or points back to the current node.

   iii. If the right child of the auxiliary node is null:

   - Print the value of the current node.

   - Establish a thread connection by setting the right child of auxiliary to current.

   - Move to the left child.

   iv. If the right child of auxiliary is the current node (indicating a threaded connection):

   - Remove the thread connection by setting the right child of auxiliary to null.

   - Move to the right child.

Code Solution

1) Morris preorder traversal in java 2) Morris preorder traversal in c++ 3) Morris preorder traversal in c 4) Morris preorder traversal in golang 5) Morris preorder traversal in c# 6) Morris preorder traversal in vb.net 7) Morris preorder traversal in php 8) Morris preorder traversal in node js 9) Morris preorder traversal in typescript 10) Morris preorder traversal in python 11) Morris preorder traversal in ruby 12) Morris preorder traversal in scala 13) Morris preorder traversal in kotlin 14) Morris preorder traversal in swift

Time Complexity

The Morris Traversal algorithm has a time complexity of O(n) where n is the number of nodes in the binary tree. This is because each edge of the tree is traversed exactly twice: once while establishing the thread connections and once while removing them.