Introduction to Threaded Binary Tree

What is Threaded Binary Tree??

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.   

  • We have the pointers reference the next node in an inorder traversal; 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 pointers. We can use these pointers to help us in inorder traversals.
  • Threaded binary tree makes the tree traversal faster since we do not need stack or recursion for traversal

Types of threaded binary trees:

  • Single Threaded: each node is threaded towards either the in-order predecessor or successor (left orright) means all right null pointers will point to inorder successor OR all left null pointers will point to inorder predecessor.
  • Double threaded: each node is threaded towards both the in-order predecessor and successor (left andright) means all right null pointers will point to inorder successor AND all left null pointers will point to inorder predecessor.
Single and Double threaded binary tree (1)

Single and Double threaded binary tree (1)

We will  see the complete implementation of both types in next articles – Single threaded binary tree , double threaded binary tree

 

Source:

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

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: