Tree Traversal -IV

Question 1: Traverse inorder without recursion and without stack
Question 2:
Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order. For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5
                                                                            4
                                                                   /                \
                                                               2                    5
                                                          /        \
                                                       1           3

Morris Inorder traversal:

The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.


           8
          /   \
        5      17
      /  \
    2     7

For above tree When we are are at 8 we find inorder predecessor of 8 =7 and point right of 7 to 8.When we are at 5 we point right of 2 to 5 [ as 5 in inorder successor of 2].We also restore the tree when we come back from 2 to 5 using right of 2.


The algorithm for Morris traversal is

    Initialize current as root
    While current is not NULL
        If current does not have left child
            Print current's data
            Go to the right, i.e., current = current->right
        Else
            Make current as right child of the rightmost node in current's left sub-tree
            Go to this left child, i.e., current = current->left

Code:

#include<stdio.h>
#include<stdlib.h>

struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return;

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}


struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;

  return(tNode);
}


int main()
{

  /* Constructed binary tree is
            8
          /   \
        5      17
      /  \
    2     7
  */
  struct tNode *root = newtNode(8);
  root->left        = newtNode(5);
  root->right       = newtNode(17);
  root->left->left  = newtNode(2);
  root->left->right = newtNode(7);

  MorrisTraversal(root);

  getchar();
  return 0;
}

Sorted order printing

Strategy:Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in standard Inorder Tree Traversal.

void printSorted(int arr[], int start, int end)

{

  if(start > end)

    return;

  // print left subtree

  printSorted(arr, start*2 + 1, end);

  printf("%d  ", arr[start]);

  // print right subtree

  printSorted(arr, start*2 + 2, end);

}

Time Complexity:O(n)