What is Threaded Binary Tree?

It is a binary tree where leaf node is threaded towards both the in-order pre­de­ces­sor or  suc­ces­sor (left or right) means all right null point­ers will point to inorder suc­ces­sor or all left null point­ers will point to inorder predecessor.

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node

 

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

ref: https://upload.wikimedia.org/wikipedia/commons/7/7a/Threaded_tree.svg

Types of threaded binary trees:

  • Sin­gle Threaded:
    • Each leaf node is threaded towards either the in-order pre­de­ces­sor or suc­ces­sor (left or right) means all right null point­ers will point to an inorder suc­ces­sor OR all left null point­ers will point to an inorder predecessor.

  • Dou­ble threaded: 
    • Each leaf node is threaded towards both the in-order pre­de­ces­sor and suc­ces­sor (left and right) means all right null point­ers will point to an inorder suc­ces­sor AND all left null point­ers will point to an inorder predecessor.