# Introduction to Threaded Binary Tree

A binary tree is threaded by mak­ing all right child point­ers that would nor­mally be null point to the inorder suc­ces­sor of the node (if it exists), and all left child point­ers that would nor­mally be null point to the inorder pre­de­ces­sor of the node.

• We have the point­ers ref­er­ence the next node in an inorder tra­ver­sal; called threads
• We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

Why do we need Threaded Binary Tree?

• Binary trees have a lot of wasted space: the leaf nodes each have 2 null point­ers. We can use these point­ers to help us in inorder traversals.
• Threaded binary tree makes the tree tra­ver­sal faster since we do not need stack or recur­sion for traversal

• Sin­gle Threaded: each node is threaded towards either the in-order pre­de­ces­sor or suc­ces­sor (left orright) means all right null point­ers will point to inorder suc­ces­sor OR all left null point­ers will point to inorder predecessor.
• Dou­ble threaded: each node is threaded towards both the in-order pre­de­ces­sor and suc­ces­sor (left andright) means all right null point­ers will point to inorder suc­ces­sor AND all left null point­ers will point to inorder predecessor.

Sin­gle and Dou­ble threaded binary tree (1)

We will  see the com­plete imple­men­ta­tion of both types in next arti­cles — Sin­gle threaded binary tree , dou­ble threaded binary tree

Source:

http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt