Immutability in C# Part Seven: More on Binary Trees

Immutability in C# Part Seven: More on Binary Trees

Rate This
  • Comments 21

Lots of good comments on my previous post. To briefly follow up:

  • One of the downsides of immutable tree implementations is that usually the tree must be built from the leaves up, which is not always convenient. We'll look at implementations which hide this fact from the user in future posts.
  • One smartypants pointed out that sure, this tree can have cycles -- if you have another binary tree implementation that has cycles and then paste such a cyclic tree in. True; what I meant was that using only the stated implementation, it's impossible to create a tree with cycles. If you are hell bent on making a bad tree, you can surely do that. Again, in a future post we'll have a tree which is built up by calling tree "mutating" operations, and those really will be guaranteed acyclic even in a world where there are other bad implementations hanging around.

And finally, one reader correctly identified the problem with my recursive implementation of in-order iteration. A tree of maximum height h ends up allocating O(h) iterator objects. The recursive calls get O(h) deep. If h is very large, this could blow the call stack. And if the tree has n nodes, each with an average height of O(h), then iterating each node will require O(h) recursive calls apiece. Therefore the total time cost in calls for iterating the entire tree is O(n h). 

In a binary tree with n nodes, h is always between log n and n, so that means that this iterator has best case asymptotic performance of O(n log n) and worst case  of O(n2) in time, and uses between O(log n) and O(n) in both call stack and heap space. That's pretty lousy.

A better implementation would be to write a tree traversal algorithm which does not use recursion. Use an explicit stack rather than the call stack:

public static IEnumerable<T> InOrder<T>(this IBinaryTree<T> tree)
{
    IStack<IBinaryTree<T>> stack = Stack<IBinaryTree<T>>.Empty;
    for (IBinaryTree<T> current = tree; !current.IsEmpty || !stack.IsEmpty; current = current.Right)
    {
        while (!current.IsEmpty)
        {
            stack = stack.Push(current);
            current = current.Left;
        }
        current = stack.Peek();
        stack = stack.Pop();
        yield return current.Value;
    }
}

This consumes O(n) time, O(h) heap space, and O(1) call stack space. It is also painful to read and analyze compared to the slow naive implementation.

I would very much like to add new syntax to a hypothetical future version of C# which would be a syntactic sugar for the code above. If, hypothetically, we were prioritizing features for unannounced future versions of C#, unfortunately that one would not be our highest priority, so I wouldn't expect it any time soon. My colleague Wes has written a great article that goes into more details about the problem above and ways we might solve it in the future, so check that out if you want the details.

I have the code for the next few blog posts written, but odds are good that I'm not going to have time to write the surrounding text until after the festive holiday season is over. I hope you have a wonderful time during the remainder of 2007 and we'll see you bright and early in 2008 for more fabulous adventures!

  • Great series!!

    Tree traversal can also be done without using stack. For example, http://vadmyst.blogspot.com/2007/09/non-recursive-binary-tree-traversal.html. But, this approach makes tree node more "heavy" as additional information has to be used.

  • In your approach how do you traverse the tree for a second time? All the nodes will be marked as visited.

    I think what you want to do is store the "visited" information in a separate dictionary object which is owned by the traverser.

  • You could make Visited an integer, incrementing it each time you visit a node.

    Obviously, it also doesn't work for immutable trees :-)

  • I should say "incrementing it each time you TRAVERSE THE TREE"...

  • Dictionary approach seems to be better, in scenarios when traversing is done only with search purpose. In this case not all nodes will be visited and "visited" counter can be useless.

  • Perhaps a nice feature of a future C# would be to allow a function to delegate the yield ability to some deeper function. That would allow you to write InOrder like this maybe:

    public static IEnumerable<T> InOrder<T>(this IBinaryTree<T> tree) { yield tree.left.InOrder(); yield return tree.value; yield tree.right.InOrder(); }

    Of course that's not a trivial feature to implement, but maybe someday C# will have continuations.

  • The InOrder function should be checking against IsEmpty instead of null or Count > 0.

    And speaking of null, it would be a nice feature to be able to specify that a variable of a class can not be set to null.  This would simplify code so that we would not have to check that a value passed into a method is null because it would not be allowed by the compiler.  This would require being able to identity a default value so that an array could be initialized.  In the case of these immutible data structues, the default would of course by Empty.

  • "I would very much like to add new syntax to a hypothetical future version of C# which would be a syntactic sugar for the code above."

    It's called F#.

  • Whoops, that's what I get for modifying the code from another project and posting it without compiling it. Thanks for the note.

  • I've a small question unrelated to this immutables series, but I hope is still relevant for this blog:

    Why did you not include generic properties/indexers in C#? Are you contemplating doing so in the "hypothetical future version of C#".

  • Why do we have to bother about "out-of-stack". Using the stack for recursion in trees are done in functional programming like F#, Lisp all the time.

    The only datastructure too big to use the stack is lists and similar, which can be several thousand elements. Trees on the other seldom becomes deeper than 100 levels, especially if you use balanced trees like AVL or red-black trees.

  • Stackless in-order binary tree traversal with left, right and parent pointers only

    Off the top of my head and untested

    class Node {

     Node Parent;

     Node Left;

     Node Right;

     Object Value;

    }

    class InOrderTreeWalk {

     bool descendLeft;

     Node current;

     InOrderTreeWalk(Node start) {

       this.descendLeft = true;

       this.current = start;

     }

     bool moveNext() {

       if(this.current == null) {

         return false;

       }

       if(this.descendLeft) {

         this.descendLeft = false;

         while(this.current.left != null) {

           this.current = this.current.left;

         }

       }

       else {

         if(this.current.right != null) {

           this.current = this.current.right;

           while(this.current.left != null) {

             this.current = this.current.left;

           }

         }

         else {

           if(this.current.parent != null && this.current == this.current.parent.left) {

              this.current = this.current.parent;

           }

           else {

             while(this.current.parent != null && this.current == this.current.parent.right) {

               this.current = this.current.parent;

             }

             if(this.current.parent == null) {

               this.current = null;

             }

           }

         }

       }

       return this.current != null;

     }

     object getValue() {

       return (this.current != null) ? this.current.Value : null;

     }

    }

  • Note that in Ifeanyi's code you are still using an additional O(n) memory for the parent pointers vs Eric's b-tree implementation. A binary tree already takes up O(n) memory for n nodes though, so you could just add it together and get back O(n) total memory usage. This doesn't sound so bad in theory.

    On the other hand, if you are using a balanced binary search tree, with recursion or explicit stack a traversal will only use O(log n) for extra memory. In practice it will then use less memory, as you'd have to run O(n/logn) traversals concurrently for it to actually use more.

  • How are you going to build an immutable binary tree that has parent pointers?

  • Note that "binary tree" and "b tree" are two entirely different data structures. "b tree" is NOT short for "binary tree".

Page 1 of 2 (21 items) 12