Morris Traversal

Problem Statement

Given a binary tree, we need to traverse the tree (visit and print the nodes of the need) without using a stack or recursion.

Example

Input tree is:

Output: The Morris traversal (in order) of the binary tree is: 4, 2, 5, 6, 1, 3.

Example Explanation

Before getting into the example explanation of how the Morris traversal is performed, let us first get a brief introduction about the in-order and pre-order traversal algorithms as we will be using both of them further.

In the in-order tree traversal we first traverse the left subtree, then the root node, and finally the right subtree. The pseudo-code for the in-order traversal can be:

1. If the current node has a left child, recursively visit the left subtree (until NULL is found).
2. Visit the root node.
3. If the current node has the right child, recursively visit the right subtree (until NULL is found).

On the other hand, in the pre-order tree traversal, we first traverse the root node, then the left subtree, and finally the right subtree.

The pseudo-code for the pre-order traversal can be:

1. Visit the root node.
2. If the current node has a left child, recursively visit the left subtree (until NULL is found).
3. If the current node has the right child, recursively visit the right subtree (until NULL is found).

Let us take the above tree and see how the Morris traversal is performed.

Morris traversal (whether pre-order or in-order or post-order) is performed on a threaded binary tree. A threaded binary tree has a thread or link that points to some ancestor node. Due to this thread linkage, we do not need to use any extra data structure or recursion to traverse the entire tree. Refer to the image provided below to see how the threaded binary tree will look.

Now, if we break the tree into smaller subtrees then we can traverse the tree without using recursion. Let us divide the tree and build the analogy.

Suppose that we are currently at the node-6, as we can see that the node does not have any left or right child so we can move back to its major parent using thread i.e move back to the node-1. Hence, we do not require any recursive approach, a link is there that will help us to get back to the place where we started.

Input/Output

Input: The provided binary tree is:

      1
    /   \
   2     3
 /   \
4     5

Output: The Morris traversal (pre-order) of the binary tree is: 1, 2, 4, 5, 3.

Constraints

• $1$ <= Number of nodes <= $10^4$
• $0$ <= Data of a node <= $10^5$

In some problems, you may find the number of test cases represented by t. So, we only need to call the MorrisTraversal() function t-times.

Algorithm - Morris Traversal for Pre-order Without Using Recursion and Stack

We have already discussed how we can traverse the entire binary tree without using any extra data structure or recursion with the help of the thread binary tree concept. We will create links to the successor nodes and after traversing we will modify the links to get back to the original binary tree.

Let us see the pseudo-code to understand the algorithm better.

Algorithm

1. Initialize the root node as the current node (currentNode).
2. If the left child of the current node is null then print the data of the current node and move to the right child.
3. Else (current node has a left child), make the right child of the in-order predecessor point to the current node.
4. Now, if the right child of the in-order predecessor is already pointing to the current node then make the right child NULL and move to the right child of the current node.
5. Else (the right child of the in-order predecessor is NULL) then sets the right child as the current node. Now, print the data of the current node and move to the left child of the current node.
6. Perform the above-mentioned steps until the current node does not become NULL.

Code Implementation

C++ Code:

Java Code:

Python code:

Output

In the Morris traversal, we are traversing the entire binary tree only once. In the traversal, we are not using any extra data structure like a stack. We are following the iterative approach.

Time Complexity

In the Morris traversal, we are traversing the binary tree only once. So, the time complexity of the Morris traversal comes out to be O(n), where n is the size of the binary tree or the number of nodes present in the binary tree.

Space Complexity

In the Morris traversal, we are traversing the binary tree only once and for the traversal, we are not using any extra data structure, we are only using an extra pointer. So, the space complexity of the Morris traversal comes out to be O(1).