Morris traversal for Preorder

Morris traversal is a way to traverse a binary tree in-order without using recursion or a stack. In Morris traversal, we make use of the right child pointer of each node to navigate through the tree in a specific manner.

When we talk about Morris traversal for pre-order, we are referring to a specific way of using Morris traversal to perform pre-order traversal of a binary tree. In this approach, we visit the node first, then traverse the left subtree and finally traverse the right subtree.

The steps involved in Morris traversal for pre-order are:

1. Initialize the current node as the root of the binary tree.
2. While the current node is not null:
   • If the left child of the current node is null, visit the current node and move to its right child.
   • If the left child of the current node is not null, find the rightmost node in the left subtree of the current node.
     • If the right child of this rightmost node is null, set it to the current node, visit the current node and move to its left child.
     • If the right child of this rightmost node is not null, set it to null and move to the right child of the current node.

By following these steps, we can traverse the binary tree in pre-order using Morris traversal without using recursion or a stack.