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.

See also

Threaded Binary Tree on Wikipedia

Written for the Swift Algorithm Club by Jayson Tung Migrated to Swift 3 by Jaap Wijnen

Images made using www.draw.io