using System;

public class Test
{
	class Node
        {
            public Node Left { get; protected set; }
            public Node Right { get; protected set; }
            public Node Parent { get; protected set; }
            public Node Next { get; set; }

            public int Value { get; set; }

            public Node(int val)
            {
                Value = val;
            }

            public Node(int val, Node l, Node r) : this(val)
            {
                SetNodes(l, r);
            }

            public void SetNodes(Node l, Node r)
            {
                if (l != null) l.Parent = this;
                if (r != null) r.Parent = this;

                Left = l;
                Right = r;
            }

            public void SetAsParent(Node p)
            {
                if (p.Left == null)
                    p.Left = this;
                else if (p.Right == null)
                    p.Right = this;
                else
                    throw new Exception("Busy");
            }
        }

        static void Main(string[] args)
        {
        	Node leaf1 = new Node(1);
        	Node leaf2 = new Node(2);
        	Node leaf3 = new Node(3);
        	Node mid1 = new Node(4, leaf1, null);
        	Node mid2 = new Node(5, leaf2, leaf3);
        	Node root = new Node(6, mid1, mid2);
        	
            root.Next = root.Left;
            Link(root);

            for (var r = root; r != null; r = r.Next)
            {
                Console.Write(r.Value + "  ");
            }
            Console.Write("\r\n");
        }

        static void Link(Node n)
        {
            if (n == null)
                return;

            if (n.Left != null)
                n.Left.Next = n.Right;

            if (n.Right != null)
                n.Right.Next = n.Next.Left;

            Link(n.Left);
            Link(n.Right);
        }
}