Threaded Binary Tree

A threaded binary tree is a special kind of binary tree (a
tree in which each node has at most two children) that maintains a few extra
variables to allow cheap and fast in-order traversal of the tree. We will
explore the general structure of threaded binary trees, as well as
the Swift implementation of a fully functioning
threaded binary tree.

If you don't know what a tree is or what it is for, then
read this first.

In-order traversal

The main motivation behind using a threaded binary tree over a simpler and
smaller standard binary tree is to increase the speed of an in-order traversal
of the tree. An in-order traversal of a binary tree visits the nodes in the
order in which they are stored, which matches the underlying ordering of a
binary search tree. This means most threaded binary
trees are also binary search trees. The idea is to visit all the left children
of a node first, then visit the node itself, and then visit the right children
last.

An in-order traversal of any binary tree generally goes as follows (using Swift
syntax):

func traverse(n: Node?) {
  if (n == nil) { return
  } else {
    traverse(n.left)
    visit(n)
    traverse(n.right)
  }
}

Where n is a a node in the tree (or nil), each node stores its children as
left and right, and "visiting" a node can mean performing any desired
action on it. We would call this function by passing to it the root of the
tree we wish to traverse.

While simple and understandable, this algorithm uses stack space proportional
to the height of the tree due to its recursive nature. If the tree has n
nodes, this usage can range anywhere from O(log n) for a fairly balanced
tree, to O(n) to a very unbalanced tree.

A threaded binary tree fixes this problem.

For more information about in-order traversals see here.

Predecessors and successors

An in-order traversal of a tree yields a linear ordering of the nodes. Thus
each node has both a predecessor and a successor (except for the first
and last nodes, which only have a successor or a predecessor respectively). In
a threaded binary tree, each left child that would normally be nil instead
stores the node's predecessor (if it exists), and each right child that would
normally be nil instead stores the node's successor (if it exists). This is
what separates threaded binary trees from standard binary trees.

There are two types of threaded binary trees: single threaded and double
threaded:

A single threaded tree keeps track of either the in-order predecessor
or successor (left or right).
A double threaded tree keeps track of both the in-order predecessor
and successor (left and right).

Using a single or double threaded tree depends on what we want to accomplish.
If we only need to traverse the tree in one direction (either forward or
backward), then we use a single threaded tree. If we want to traverse in both
directions, then we use a double threaded tree.

It is important to note that each node stores either its predecessor or its
left child, and either its successor or its right child. The nodes do not
need to keep track of both. For example, in a double threaded tree, if a node
has a right child but no left child, it will track its predecessor in place of
its left child.

Here is an example valid "full" threaded binary tree:

While the following threaded binary tree is not "full," it is still valid. The
structure of the tree does not matter as long as it follows the definition of a
binary search tree:

The solid lines denote the links between parents and children, while the dotted
lines denote the "threads." It is important to note how the children and
thread edges interact with each other. Every node besides the root has one
entering edge (from its parent), and two leaving edges: one to the left and one
to the right. The left leaving edge goes to the node's left child if it
exists, and to its in-order predecessor if it does not. The right leaving edge
goes to the node's right child if it exists, and to its in-order successor if
it does not. The exceptions are the left-most node and the right-most node,
which do not have a predecessor or successor, respectively.

Representation

Before we go into detail about the methods of a threaded binary tree, we should
first explain how the tree itself is represented. The core of this data
structure is the ThreadedBinaryTree<T: Comparable> class. Each instance of
this class represents a node with six member variables: value, parent,
left, right, leftThread, and rightThread. Of all of these, only
value is required. The other five are Swift optionals (they may be nil).

value: T is the value of this node (e.g. 1, 2, A, B, etc.)
parent: ThreadedBinaryTree? is the parent of this node
left: ThreadedBinaryTree? is the left child of this node
right: ThreadedBinaryTree? is the right child of this node
leftThread: ThreadedBinaryTree? is the in-order predecessor of this node
rightThread: ThreadedBinaryTree? is the in-order successor of this node

As we are storing both leftThread and rightThread, this is a double
threaded tree. Now we are ready to go over some of the member functions in our
ThreadedBinaryTree class.

Traversal algorithm

Let's start with the main reason we're using a threaded binary tree. It is now
very easy to find the in-order predecessor and the in-order successor of any
node in the tree. If the node has no left/right child, we can simply
return the node's leftThread/rightThread. Otherwise, it is trivial to move
down the tree and find the correct node.

  func predecessor() -> ThreadedBinaryTree<T>? {
    if let left = left {
      return left.maximum()
    } else {
      return leftThread
    }
  }

  func successor() -> ThreadedBinaryTree<T>? {
    if let right = right {
      return right.minimum()
    } else {
      return rightThread
    }
  }

Note: maximum() and minimum() are methods of ThreadedBinaryTree which
return the largest/smallest node in a given sub-tree. See
the implementation for more detail.

Because these are ThreadedBinaryTree methods, we can call
node.predecessor() or node.successor() to obtain the predecessor or
successor of any node, provided that node is a ThreadedBinaryTree object.

Because predecessors and/or successors are tracked, an in-order traversal of a
threaded binary tree is much more efficient than the recursive algorithm
outlined above. We use these predecessor/successor attributes to great effect
in this new algorithm for both forward and backward traversals:

    public func traverseInOrderForward(_ visit: (T) -> Void) {
        var n: ThreadedBinaryTree
        n = minimum()
        while true {
            visit(n.value)
            if let successor = n.successor() {
                n = successor
            } else {
                break
            }
        }
    }

    public func traverseInOrderBackward(_ visit: (T) -> Void) {
        var n: ThreadedBinaryTree
        n = maximum()
        while true {
            visit(n.value)
            if let predecessor = n.predecessor() {
                n = predecessor
            } else {
                break
            }
        }
    }

Again, this a method of ThreadedBinaryTree, so we'd call it via
node.traverseInorderForward(visitFunction). Note that we are able to specify
a function that executes on each node as they are visited. This function can
be anything you want, as long as it accepts T (the type of the values of the
nodes of the tree) and has no return value.

Let's walk through a forward traversal of a tree by hand to get a better idea
of how a computer would do it. For example, take this simple threaded tree:

We start at the root of the tree, 9. Note that we don't visit(9) yet.
From there we want to go to the minimum() node in the tree, which is 2 in
this case. We then visit(2) and see that it has a rightThread, and thus
we immediately know what its successor() is. We follow the thread to 5,
which does not have any leaving threads. Therefore, after we visit(5), we go
to the minimum() node in its right subtree, which is 7. We then
visit(7) and see that it has a rightThread, which we follow to get back to
9. Now we visit(9), and after noticing that it has no rightThread,
we go to the minimum() node in its right subtree, which is 12. This
node has a rightThread that leads to nil, which signals that we have
completed the traversal! We visited the nodes in order 2, 5, 7, 9, 12,
which intuitively makes sense, as that is their natural increasing order.

A backward traversal would be very similar, but you would replace right,
rightThread, minimum(), and successor() with left, leftThread,
maximum(), and predecessor().

Insertion and deletion

The quick in-order traversal that a threaded binary trees gives us comes at a
small cost. Inserting/deleting nodes becomes more complicated, as we have to
continuously manage the leftThread and rightThread variables. Rather than
walking through some boring code, it is best to explain this with an example
(although you can read through the implementation
if you want to know the finer details). Please note that this requires
knowledge of binary search trees, so make sure you have
read this first.

Note: we do allow duplicate nodes in this implementation of a threaded binary
tree. We break ties by defaulting insertion to the right.

Let's start with the same tree that we used for the above traversal example:

Suppose we insert 10 into this tree. The resulting graph would look like
this, with the changes highlighted in red:

If you've done your homework and are familiar with binary search trees, the
placement of this node should not surprise you. What's new is how we maintain
the threads between nodes. So we know that we want to insert 10 as
12's left child. The first thing we do is set 12's left child to
10, and set 10's parent to 12. Because 10 is being inserted
on the left, and 10 has no children of its own, we can safely set
10's rightThread to its parent 12. What about 10's
leftThread? Because we know that 10 < 12, and 10 is the only
left child of 12, we can safely set 10's leftThread to 12's
(now outdated) leftThread. Finally we set 12's leftThread = nil, as it
now has a left child.

Let's now insert another node, 4, into the tree:

While we are inserting 4 as a right child, it follows the exact same
process as above, but mirrored (swap left and right). For the sake of
completeness, we'll insert one final node, 15:

Now that we have a fairly crowded tree, let's try removing some nodes.
Compared to insertion, deletion is a little more complicated. Let's start with
something simple, like removing 7, which has no children:

Before we can just throw 7 away, we have to perform some clean-up. In this
case, because 7 is a right child and has no children itself, we can
simply set the rightThread of 7's parent(5) to 7's (now
outdated) rightThread. Then we can just set 7's parent, left,
right, leftThread, and rightThread to nil, effectively removing it from
the tree. We also set the parent's rightChild to nil, which completes the deletion of this right child.

Let's try something a little harder. Say we remove 5 from the tree:

This is a little trickier, as 5 has some children that we have to deal
with. The core idea is to replace 5 with its first child, 2. To
accomplish this, we of course set 2's parent to 9 and set 9's
left child to 2. Note that 4's rightThread used to be 5, but
we are removing 5, so it needs to change. It is now important to
understand two important properties of threaded binary trees:

For the rightmost node m in the left subtree of any node n,
m's rightThread is n.
For the leftmost node m in the right subtree of any node n,
m's leftThread is n.

Note how these properties held true before the removal of 5, as 4 was
the rightmost node in 5's left subtree. In order to maintain this
property, we must set 4's rightThread to 9, as 4 is now the
rightmost node in 9's left subtree. To completely remove 5, all we
now have to do is set 5's parent, left, right, leftThread, and
rightThread to nil.

How about we do something crazy? What would happen if we tried to remove
9, the root node? This is the resulting tree:

Whenever we want to remove a node that has two children, we take a slightly
different approach than the above examples. The basic idea is to replace the
node that we want to remove with the leftmost node in its right subtree,
which we call the replacement node.

Note: we could also replace the node with the rightmost node in its left
subtree. Choosing left or right is mostly an arbitrary decision.

Once we find the replacement node, 10 in this case, we remove it from the
tree using the algorithms outlined above. This ensures that the edges in the
right subtree remain correct. From there it is easy to replace 9 with
10, as we just have to update the edges leaving 10. Now all we have to
do is fiddle with the threads in order to maintain the two properties outlined
above. In this case, 12's leftThread is now 10. Node 9 is no
longer needed, so we can finish the removal process by setting all of its
variables to nil.

In order to illustrate how to remove a node that has only a right child,
we'll remove one final node, 12 from the tree:

The process to remove 12 is identical to the process we used to remove
5, but mirrored. 5 had a left child, while 12 has a right
child, but the core algorithm is the same.

And that's it! This was just a quick overview of how insertion and deletion
work in threaded binary trees, but if you understood these examples, you should
be able to insert or remove any node from any tree you want. More detail can
of course be found in
the implementation.

Miscellaneous methods

There are many other smaller operations that a threaded binary tree can do,
such as searching() for a node in the tree, finding the depth() or
height() of a node, etc. You can check
the implementation for the full technical details.
Many of these methods are inherent to binary search trees as well, so you can
find further documentation here.