Threaded binary tree

From Wikipedia, the free encyclopedia

A threaded binary tree may be 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, and all left child pointers that would normally be null point to the inorder predecessor of the node."

(Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1989, p. 175. ISBN 0-201-16116-8.)

A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.