Optimize Recursive Fetching of information?
All right, I've done a bit of work here (a good most of it stylistic, to be sure).  Do note I replaced object with a generic implementation to help avoid boxing of value types.  It does also employ LINQ in a couple instances to remove some complexity.  When I run it and generate 1,000,000 integer leaves, I find that the bulk of the time is taken in the class constructors and the methods themselves are close enough to 0 time to be considered 0.  Hope this helps:

internal sealed class Root&lt;T&gt;
{
    private readonly Leaf&lt;T&gt; rootLeaf = new Leaf&lt;T&gt;();

    // dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
    private readonly IDictionary&lt;T, Leaf&lt;T&gt;&gt; allItems = new Dictionary&lt;T, Leaf&lt;T&gt;&gt;();

    /// &lt;summary&gt;
    /// Gets GetAllChildren.
    /// &lt;/summary&gt;
    public IList&lt;T&gt; GetAllChildren
    {
        get
        {
            return this.rootLeaf.GetAllChildren;
        }
    }

    public void Add(T o)
    {
        var addedTo = this.rootLeaf.Add(o);

        this.allItems.Add(o, addedTo); // Add object reference to AllItems dictionary
    }

    public void Update()
    {
        foreach (var i in from i in this.allItems from b in this.GetNeighbors(i.Key) select i)
        {
            // Would do collision checks here
        }
    }

    private IEnumerable&lt;T&gt; GetNeighbors(T obj)
    {
        return this.allItems[obj].GetAllChildren.Where(o =&gt; ReferenceEquals(obj, o));
    }
}

internal class Leaf&lt;T&gt;
{
    private const int MaxChildCount = 1;

    private static readonly Random rand = new Random();

    private readonly IList&lt;T&gt; children = new List&lt;T&gt;();

    private List&lt;Leaf&lt;T&gt;&gt; childLeaves;

    private bool hasLeaves; // Should we use the leaves?

    private bool leavesGenerated; // Have the leaves been created? (Low Level, do not touch)

    /// &lt;summary&gt;
    /// Returns children of this leaf, and all of its subleaves
    /// &lt;/summary&gt;
    public IList&lt;T&gt; GetAllChildren
    {
        get
        {
            var allChildren = this.children.ToList();

            if (this.hasLeaves)
            {
                this.childLeaves.ToList().ForEach(l =&gt; allChildren.AddRange(l.GetAllChildren));
            }

            return allChildren;
        }
    }

    /// &lt;summary&gt;
    /// Get count of all children in this leaf, and its subleaves
    /// &lt;/summary&gt;
    public int GetChildCount
    {
        get
        {
            var allChildrenCount = this.children.Count;

            if (this.hasLeaves)
            {
                allChildrenCount += this.childLeaves.Sum(l =&gt; l.GetChildCount);
            }

            return allChildrenCount;
        }
    }

    /// &lt;summary&gt;
    /// 
    /// &lt;/summary&gt;
    /// &lt;param name="o"&gt;The object to be added&lt;/param&gt;
    /// &lt;returns&gt;The leaf the object was added to&lt;/returns&gt;
    public Leaf&lt;T&gt; Add(T o)
    {
        if (this.children.Count &lt; MaxChildCount)
        {
            this.children.Add(o);
            return this;
        }

        // Pick random subleaf, I know this isn't correct for a quadtree, but it will simplify this explanation code
        if (!this.hasLeaves)
        {
            this.CreateLeaves();
        }

        return this.childLeaves[rand.Next(0, 3)].Add(o);
    }

    protected void CreateLeaves()
    {
        if (!this.leavesGenerated)
        {
            // create each of the four leaves
            this.childLeaves = new List&lt;Leaf&lt;T&gt;&gt; { new Leaf&lt;T&gt;(), new Leaf&lt;T&gt;(), new Leaf&lt;T&gt;(), new Leaf&lt;T&gt;() };

            this.leavesGenerated = true;
        }

        this.hasLeaves = true;
    }

    protected void RemoveLeaves()
    {
        this.hasLeaves = false;
    }
}