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