Threaded binary tree

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

Linked lists thus defined are also commonly called "threads", and can be used to enable traversal in any order(s) desired.

For example, a tree whose nodes represent information about people might be sorted by name, but have extra threads allowing quick traversal in order of birth date, weight, or any other known characteristic.

A simple recursive traversal algorithm that visits each node of a binary search tree is the following.

In a 1968 textbook, Donald Knuth asked whether a non-recursive algorithm for in-order traversal exists, that uses no stack and leaves the tree unmodified.

[3][4] In the 1969 follow-up edition,[5] Knuth attributed the threaded tree representation to Perlis and Thornton (1960).

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.