Non-Recursive (Morris) In-Order Traversal and Recursive In-Order Traversal in C#

Morris In-Order traversal traverses the given tree in in-order without using Recursion or Stack. Morris In-Order traversal uses concept of threading the nodes, which are either leaves or which do not have right node to their in-order successors. This allows traversing back in in-order hierarchy simple. Traversal also removes the links that are created for this purpose and keep the tree unchanged.

Steps involved in Morris traversal are:

1. Get the in-order predecessor of current node: In-order successor of any given node in BST is a node's left node's right most element.

2. When you reach such in-order predecessor for current node, since that node will be either be a leaf node or a node that does not have right child. Make current as right child of that in-order predecessor and move current node pointer to its left item.

3. A temporary pointer "pre" is used to find out the in-order predecessor of given node "current". "pre.Right = current; " is used to thread in-order predecessor node to its successor.

4. When current moves to the left most element in the tree, print the data of the node and move current to current's right. This is important. It uses previously created link to move to in-order successor of current.

5. Then to remove this link, we follow finding in-order predecessor procedure until pre-Right points to current node itself. That means there is a link between current and the node "pre" is pointing to. Since we have already visited that node, we shall break this link, by setting pre.Right = null. We also shall print this "current" node data and then move to its in-order successor using the links that we created in earlier steps.

6. When pre.Right == Current means  there is a link that we created between pre and current. We shall break link and proceed to next in-order successor using Current = current.Right;

7. Also Current = current.Right when (pre.Right== current) assures that after left tree is processed, we move right part of the given binary search tree.

8. When Current moves to left most node of the tree, i.e. if Current.Left == null then Current= current.Right assures we traverse back to its in-order successor using the link that we already created.


Below code also includes a method which does recursive in-order traversal in order to compare with Morris traversal.

Complete Code:
=======================================================================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            Node root = new Node();
            root.Data = 6;
            root.Left = new Node(4);
            root.Left.Right = new Node(5);
            root.Right = new Node(10);
            root.Left.Left = new Node(2);
            root.Left.Left.Left = new Node(1);
            root.Right.Left = new Node(8);
            root.Right.Left.Right = new Node(9);
            root.Right.Left.Left = new Node(7);
            root.Right.Right = new Node(14);
            root.Right.Right.Left = new Node(13);
            root.Right.Right.Left.Left = new Node(12);
            root.Right.Right.Right = new Node(17);


            PrintInorderTraversal(root);
            Console.WriteLine("");
            Add(root, 3);
            Add(root, 11);


            PrintInorderTraversal(root);
            Console.WriteLine("");
            Console.WriteLine("morris inorder travesal using threading");
            Console.WriteLine("");
            MorrisInorderTraversal(root);
            Console.ReadLine();




        }


        static void MorrisInorderTraversal(Node root)
        {
            Node current = root;
            Node pre = null;
            while (current != null)
            {
                //it is looping back to parent
                //using already threaded leaf and node in hierarchy
                if (current.Left == null)
                {
                    Console.Write(current.Data + " ");
                    current = current.Right;
                }
                else
                {
                    //now find the inorder predeccsor or current node
                    pre = current.Left;
                    while (pre.Right != null && pre.Right != current)
                    {
                        pre = pre.Right;
                    }
                    if (pre.Right == null)
                    {
                        //inorder predeccesor found
                        //move current to left again
                        pre.Right = current;
                        current = current.Left;
                    }
                    else
                    {
                        //after every thread is been created from a node which does not have a right node
                        //to its inorder successor
                        //now lets visit that inorder successor using right pointer


                        //lets print the data and move to right i.e go up to inorder successor                        
                        pre.Right = null;
                        Console.Write(current.Data+" ");
                        current = current.Right;
                    }


                }
            }
        }
        static void PrintInorderTraversal(Node current)
        {
            if (current != null)
            {
                PrintInorderTraversal(current.Left);
                Console.Write(current.Data+" ");
                PrintInorderTraversal(current.Right);
            }
        }


        static void Add(Node root, int data)
        {
            Node current = root; Node Parent = null;
            Node temp = new Node(data);
            while (current != null)
            {
                if (current.Data > data)
                {
                    Parent = current;
                    current = current.Left;
                }
                else if(current.Data < data)


                {
                    Parent = current;
                    current = current.Right;
                }
                else
                {
                    //duplicte value
                    return;
                }               
            }
            //empty tree
            if (Parent == null)
            {
                root = temp;
            }
            else
            {


                if (Parent.Data > data)
                {
                    Parent.Left = temp;
                }
                else
                {
                    Parent.Right = temp;
                }
            }
        }
    }


    public class Node
    {
        int data;


        public Node()
        {
        }


        public int Data
        {
            get { return data; }
            set { data = value; }
        }
        Node left = null;


        public Node Left
        {
            get { return left; }
            set { left = value; }
        }


        Node right =null;


        public Node Right
        {
            get { return right; }
            set { right = value; }
        }


        public Node(int v)
        {
            data = v;
        }        
    }
}

=======================================================================

Reference & Thanks: GeeksForGeeks.org