Threaded binary tree
lastmod 2015-11-06created 2015-11-061 edits
A threaded binary tree is a type of binary tree in which every right null pointer that points nowhere is linked to the in-order successor node, and every left null pointer that points nowhere is linked to the in-order predecessor node. It is used as a way to speed up recursive in-order traversal.
It also makes it possible to find a node's parent in a threaded binary tree without using a parent pointer or a stack, albeit somewhat more slowly. This can be useful when stack space is unavailable or when the location of the parent node is unknown.