Idiomatic Traversal Binary Tree (Perhaps Any Tree)

Question

A Doubly Linked List enables idiomatic traversal of a Linked List and I thought why not for a Binary Tree? Traditionally, Binary Trees or Trees ingeneral are unidirectional and that implies, given a large tree with sufficient number of nodes, the running time to find a leaf node can be costly.

If, after finding such a node, to find the next I could traverse the tree back toward the root, would that not be advantageous as compared to another depth-first search through every node of the tree? I have never considered this before until realizing the marriage of a Doubly Linked List and a Binary Tree could potentially add benefit.

For example, if I employed an inner class

class Tree<T> {

      private class TwoWayNode {

           var data     : T
           var left     : TwoWayNode
           var right    : TwoWayNode
           var previous : TwoWayNode
      }
}

The use of left and right are as normal to traverse the respective subtrees from each node and previous would hold a pointer to the parent node enable idiomatic traversal. Would someting like this work well and what are some of the potential problems or pitfalls?

Answer 1

Given you store a previous reference, you can walk leftmost first. Upon arrival at the leaf node, you back one up again, traverse right.

You can always compare the current node, your "walker", with the child nodes, so you can check if you went left or right the last time. This makes your traversal stateless and you do not even need recursion; suitable for very large datasets.

Now, everytime you just left the right leaf, you back one up again.

This algorithm is a Depth-First-Search.^*

Making it faster: Given that you could define some deterministic condition for the order of traversal, this can become quite flexible, and even be used in applications like ray tracing.

---

^*: http://en.wikipedia.org/wiki/Depth-first_search

Bonus: This paper on traversal algorithms for Kd-trees in Ray Tracing: Review: Kd-tree Traversal Algorithms for Ray Tracing (http://dcgi.felk.cvut.cz/home/havran/ARTICLES)/cgf2011.pdf

Answer 2

Indeed nodes of a binary tree are often implemented with pointers to the left and right child and the parent (see this implementation of red black trees).

But you not always need a parent pointer:

• For an inorder-traversal you can use a recursive algorithm so that the call stack takes care of that for you.
• If you want to access the min or max node you can simply maintain a extra pointer to them.
• Sometimes you can use a finger tree.
• Or organize your pointers extra clever (see Self adjusting binary search trees page 666):
  • The left pointer of a node points to the first (left) child
  • The right pointer of a node points to either the sibling (if it is a left child) or back to the parent (if it is a right child)

Extra cool: Threaded binary search trees for extra easy inorder (and reverse order) traversal without a stack - so O(1) space!