Introduction to Threaded Binary Tree

What is 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

Types of threaded binary trees:

  • 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.
Single and Double threaded binary tree (1)

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

https://en.wikipedia.org/wiki/Threaded_binary_tree

You may also like...