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)
            {
                l.Parent = this;
                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)
        {
            for (var xx = 1; xx < 20; xx++)
            {
                var hA = new Node[xx];
                hA[0] = new Node(0);

                for (int i = 1; i < hA.Length; i++)
                {
                    hA[i] = new Node(i);

                    hA[i].SetAsParent(hA[(i + 1) / 2 - 1]);
                }

                var root = hA[0];
                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);
        }
}