Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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...