NetGore

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
        }
    }
 
    class Node
    {
        Node _left;
        Node _right;
        Node _parent;
 
        /// <summary>
        /// Gets if this node is a leaf node (has no children).
        /// </summary>
        public bool IsLeaf { get { return Left == null && Right == null; } }
 
        /// <summary>
        /// Gets if this node is a root node (has no parent).
        /// </summary>
        public bool IsRoot { get { return Parent == null; } }
 
        /// <summary>
        /// Gets all of the nodes under this node on both the left and right branches, but not including this node.
        /// </summary>
        public IEnumerable<Node> Nodes
        {
            get
            {
                // Grab the left side
                if (Left != null)
                {
                    // Return the node to the left
                    yield return Left;
 
                    // Create a recursion to perform this same operation on every single node
                    foreach (var leftChildNodes in Left.Nodes)
                        yield return leftChildNodes;
                }
 
                // Do the exact same thing for the right side
                if (Right != null)
                {
                    yield return Right;
 
                    foreach (var rightChildNode in Right.Nodes)
                        yield return rightChildNode;
                }
            }
        }
 
        /// <summary>
        /// Get the depth (level) of this node in the tree, where the root node is the a depth of 1.
        /// </summary>
        public int Depth
        {
            get
            {
                // Initial depth is 1
                int depth = 1;
 
                // Grab the initial node, which is the parent of this node
                var n = Parent;
 
                // Keep looping back through the tree until we hit the root node (parent == null), incrementing the
                // depth count each time
                while (n != null)
                {
                    n = n.Parent;
                    depth++;
                }
 
                return depth;
            }
        }
 
        /// <summary>
        /// Gets the parent node. Will be null if this is the root.
        /// </summary>
        public Node Parent { get { return _parent; } }
 
        /// <summary>
        /// Gets the child node on the left side.
        /// </summary>
        public Node Left
        {
            get { return _left; }
            set
            {
                _left = value;
                if (_left != null)
                    _left._parent = this; 
            }
        }
 
        /// <summary>
        /// Gets the child node on the right side.
        /// </summary>
        public Node Right
        {
            get { return _right; }
            set
            {
                _right = value;
                if (_right != null)
                    _right._parent = this;
            }
        }
    }
 
    class BinaryTree
    {
        readonly Node _root;
 
        /// <summary>
        /// Gets the root node in the tree.
        /// </summary>
        public Node Root { get { return _root; } }
 
        /// <summary>
        /// Gets all of the nodes in the tree.
        /// </summary>
        public IEnumerable<Node> Nodes
        {
            get
            {
                if (Root == null)
                    yield break;
 
                // Return the root node (since it is not included in the call to Node.Nodes)
                yield return Root;
 
                // Return all the child node in the root
                foreach (var child in Root.Nodes)
                    yield return child;
            }
        }
 
        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTree"/> class.
        /// </summary>
        public BinaryTree()
        {
            _root = new Node();
        }
    }
}

static void FillTree(Node node, int targetDepth)
        {
            // Hit the needed depth, no need to add more nodes
            if (node.Depth == targetDepth)
                return;
 
            // Add nodes to the left and right side, if needed
            if (node.Left == null)
                node.Left = new Node();
 
            if (node.Right == null)
                node.Right = new Node();
 
            // Recurse on both the sides
            FillTree(node.Left, targetDepth);
            FillTree(node.Right, targetDepth);
        }

        public uint ID
        {
            get
            {
                return GetID(1);
            }
        }
 
        uint GetID(uint id)
        {
            if (IsRoot)
                return id;
 
            id <<= 1;
 
            if (Parent.Right == this)
                id |= 1;
 
            return Parent.GetID(id);
        }

        static void Main(string[] args)
        {
            BinaryTree t = new BinaryTree();
            FillTree(t.Root, 8);
 
            foreach (var node in t.Nodes.Distinct().OrderBy(x => x.ID))
                Console.WriteLine(node.ID);
 
            Console.ReadLine();
        }

        public Node FindNode(uint id)
        {
            // Grab the first node, which is always the root
            var current = Root;
 
            // Get the bit index to start at (the left-most bit)
            var i = GetFirstSetBitIndex(id);
 
            // Keep following the tree by using the bit at "i" (0 means go right, 1 means go left) until
            // we hit the end. We do --i instead of i-- since we still have to decrement the count once
            // for the root. If current == null, then we have an invalid ID.
            while ((--i >= 0) && current != null)
            {
                if ((id & (1 << i)) != 0)
                    current = current.Left;
                else
                    current = current.Right;
            }
 
            return current;
        }
 
        /// <summary>
        /// Gets the 0-based index of the left-most set bit. For a more efficient way, see BitOps.RequiredBits in NetGore.
        /// Value will be -1 if no bits are set.
        /// </summary>
        static int GetFirstSetBitIndex(uint value)
        {
            if (value == 0)
                return -1;
 
            for (int i = 32; i > 0; i--)
            {
                if ((value & (uint)(1 << i)) != 0)
                    return i;
            }
 
            return 0;
        }

        static void Main(string[] args)
        {
            BinaryTree t = new BinaryTree();
            FillTree(t.Root, 8);
 
            // Grab a random node (whatever the 50th node is) in the tree
            var n = t.Nodes.Skip(50).First();
 
            // Get the node by using the ID
            var nFromID = t.FindNode(n.ID);
 
            // Ensure it is correct
            System.Diagnostics.Debug.Assert(n == nFromID);
        }