threaded tree

(data structure)

Definition: A binary search tree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-order successor.

Note: See [Knuth97, 1:320, Sect. 2.3.1]. Although the definition could refer to a multiway tree, Knuth defines a threaded tree as a binary tree.

Author: PEB

Implementation

Ben Pfaff's explanations and code (C)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 23 May 2011.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "threaded tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/threadedtree.html