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);
        }
}

dXNpbmcgU3lzdGVtOwoKcHVibGljIGNsYXNzIFRlc3QKewoJY2xhc3MgTm9kZQogICAgICAgIHsKICAgICAgICAgICAgcHVibGljIE5vZGUgTGVmdCB7IGdldDsgcHJvdGVjdGVkIHNldDsgfQogICAgICAgICAgICBwdWJsaWMgTm9kZSBSaWdodCB7IGdldDsgcHJvdGVjdGVkIHNldDsgfQogICAgICAgICAgICBwdWJsaWMgTm9kZSBQYXJlbnQgeyBnZXQ7IHByb3RlY3RlZCBzZXQ7IH0KICAgICAgICAgICAgcHVibGljIE5vZGUgTmV4dCB7IGdldDsgc2V0OyB9CgogICAgICAgICAgICBwdWJsaWMgaW50IFZhbHVlIHsgZ2V0OyBzZXQ7IH0KCiAgICAgICAgICAgIHB1YmxpYyBOb2RlKGludCB2YWwpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFZhbHVlID0gdmFsOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwdWJsaWMgTm9kZShpbnQgdmFsLCBOb2RlIGwsIE5vZGUgcikgOiB0aGlzKHZhbCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgU2V0Tm9kZXMobCwgcik7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHB1YmxpYyB2b2lkIFNldE5vZGVzKE5vZGUgbCwgTm9kZSByKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsLlBhcmVudCA9IHRoaXM7CiAgICAgICAgICAgICAgICByLlBhcmVudCA9IHRoaXM7CgogICAgICAgICAgICAgICAgTGVmdCA9IGw7CiAgICAgICAgICAgICAgICBSaWdodCA9IHI7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHB1YmxpYyB2b2lkIFNldEFzUGFyZW50KE5vZGUgcCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKHAuTGVmdCA9PSBudWxsKQogICAgICAgICAgICAgICAgICAgIHAuTGVmdCA9IHRoaXM7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChwLlJpZ2h0ID09IG51bGwpCiAgICAgICAgICAgICAgICAgICAgcC5SaWdodCA9IHRoaXM7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgdGhyb3cgbmV3IEV4Y2VwdGlvbigiQnVzeSIpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBmb3IgKHZhciB4eCA9IDE7IHh4IDwgMjA7IHh4KyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZhciBoQSA9IG5ldyBOb2RlW3h4XTsKICAgICAgICAgICAgICAgIGhBWzBdID0gbmV3IE5vZGUoMCk7CgogICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBoQS5MZW5ndGg7IGkrKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBoQVtpXSA9IG5ldyBOb2RlKGkpOwoKICAgICAgICAgICAgICAgICAgICBoQVtpXS5TZXRBc1BhcmVudChoQVsoaSArIDEpIC8gMiAtIDFdKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICB2YXIgcm9vdCA9IGhBWzBdOwogICAgICAgICAgICAgICAgcm9vdC5OZXh0ID0gcm9vdC5MZWZ0OwogICAgICAgICAgICAgICAgTGluayhyb290KTsKCiAgICAgICAgICAgICAgICBmb3IgKHZhciByID0gcm9vdDsgciAhPSBudWxsOyByID0gci5OZXh0KQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGUoci5WYWx1ZSArICIgICIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgQ29uc29sZS5Xcml0ZSgiXHJcbiIpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBMaW5rKE5vZGUgbikKICAgICAgICB7CiAgICAgICAgICAgIGlmIChuID09IG51bGwpCiAgICAgICAgICAgICAgICByZXR1cm47CgogICAgICAgICAgICBpZiAobi5MZWZ0ICE9IG51bGwpCiAgICAgICAgICAgICAgICBuLkxlZnQuTmV4dCA9IG4uUmlnaHQ7CgogICAgICAgICAgICBpZiAobi5SaWdodCAhPSBudWxsKQogICAgICAgICAgICAgICAgbi5SaWdodC5OZXh0ID0gbi5OZXh0LkxlZnQ7CgogICAgICAgICAgICBMaW5rKG4uTGVmdCk7CiAgICAgICAgICAgIExpbmsobi5SaWdodCk7CiAgICAgICAgfQp9