text: Morris traversal for Preorder | C program for Morris Preorder traversal ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Preorder traversal without recursion and without stack ; If left child is null , print the current node data . Move to right child . ; Find inorder predecessor ; If the right child of inorder predecessor already points to this node ; If right child doesn 't point to this node, then print this  node and make right child point to this node ; Function for sStandard preorder traversal ; Driver program to test above functions
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left , * right ; } ; struct node * newNode ( int data ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } void morrisTraversalPreorder ( struct node * root ) { while ( root ) { if ( root -> left == NULL ) { printf ( " % d ▁ " , root -> data ) ; root = root -> right ; } else { struct node * current = root -> left ; while ( current -> right && current -> right != root ) current = current -> right ; if ( current -> right == root ) { current -> right = NULL ; root = root -> right ; } else { printf ( " % d ▁ " , root -> data ) ; current -> right = root ; root = root -> left ; } } } } void preorder ( struct node * root ) { if ( root ) { printf ( " % d ▁ " , root -> data ) ; preorder ( root -> left ) ; preorder ( root -> right ) ; } } int main ( ) { struct node * root = NULL ; root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> left -> left -> right = newNode ( 9 ) ; root -> left -> right -> left = newNode ( 10 ) ; root -> left -> right -> right = newNode ( 11 ) ; morrisTraversalPreorder ( root ) ; printf ( " STRNEWLINE " ) ; preorder ( root ) ; return 0 ; }