Threaded binary tree

Motivation

Binary trees, including (but not limited to) binary search trees and their variants, can be used to store a set of items in a particular order. For example, a binary search tree assumes data items are somehow ordered and maintain this ordering as part of their insertion and deletion algorithms. One useful operation on such a tree is traversal: visiting the items in the order in which they are stored (which matches the underlying ordering in the case of BST).

A simple recursive traversal algorithm that visits each node of a BST is the following. Assume t is a pointer to a node, or nil. "Visiting" t can mean performing any action on the node t or its contents.

The problem with this algorithm is that, because of its recursion, it uses stack space proportional to the height of a tree. If the tree is fairly balanced, this amounts to O(log n) space for a tree containing n elements. In the worst case, when the tree takes the form of a chain, the height of the tree is n so the algorithm takes O(n) space.

In 1968, Donald Knuth asked whether a non-recursive algorithm for in-order traversal exists, that uses no stack and leaves the tree unmodified. One of the solutions to this problem is tree threading, presented by J. H. Morris in 1979.

Definition

A threaded binary tree defined as follows:

"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node."

It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).

To see how this is possible, consider a node k that has a right child r. Then the left pointer of r must be either a child or a thread back to k. In the case that r has a left child, that left child must in turn have either a left child of its own or a thread back to k, and so on for all successive left children. So by following the chain of left pointers from r, we will eventually find a thread pointing back to k. The situation is symmetrically similar when q is the left child of p—we can follow q's right children to a thread pointing ahead to p.

Types of threaded binary trees

1. Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right).
2. Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).

In Python:

The array of Inorder traversal

Threads are reference to the predecessors and successors of the node according to an inorder traversal.

Inorder of the threaded tree is ABCDEFGHI, the predecessor of E is D, the successor of E is F.

Let's make the Threaded Binary tree out of a normal binary tree

The INORDER traversal for the above tree is—D B A E C. So, the respective Threaded Binary tree will be --

Null link

In an m-way threaded binary tree with n nodes, there are n*m - (n-1) void links.

Non recursive Inorder traversal for a Threaded Binary Tree

As this is a non-recursive method for traversal, it has to be an iterative procedure; meaning, all the steps for the traversal of a node have to be under a loop so that the same can be applied to all the nodes in the tree. We will consider the INORDER traversal again. Here, for every node, we'll visit the left sub-tree (if it exists) first (if and only if we haven't visited it earlier); then we visit (i.e. print its value, in our case) the node itself and then the right sub-tree (if it exists). If the right sub-tree is not there, we check for the threaded link and make the threaded node the current node in consideration. Please, follow the example given below.

Algorithm

Step-1: For the current node check whether it has a left child which is not there in the visited list. If it has then go to step-2 or else step-3.

Step-2: Put that left child in the list of visited nodes and make it your current node in consideration. Go to step-6

Step-3: Print the node and If node has right child then go to step 4 else go to step 5

Step-4: Make right child as current node.

Step-5:if there is a thread node then make it the current node.

Step-6: if all nodes have been printed then END else go to step 1