page_title: Threaded binary tree
hierarchical_section_title: Threaded binary tree
context_page_description: In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order.
  An entire binary sort tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so no other node can be reached given only a pointer to a leaf node -- of course that includes the desired "next" node. A threaded tree adds extra information in some or all nodes, so the "next" node can be found quickly. It can also be traversed without recursion and the extra storage that requires.
context_section_description: In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order (often the same order already defined for the tree).
  An entire binary sort tree can be easily traversed in order of the main key, but given only a pointer to a node, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so no other node can be reached given only a pointer to a leaf node -- of course that includes the desired "next" node. A threaded tree adds extra information in some or all nodes, so the "next" node can be found quickly. It can also be traversed without recursion and the extra storage (proportional to the tree's depth) that requires.
caption: A threaded tree, with the special threading links shown by dashed arrows