Data Structure (2130702)

• The wasted NULL links in the binary tree storage representation can be replaced by threads.
• A binary tree is threaded according to particular traversal order. e.g.: Threads for the inorder traversals of tree are pointers to its higher nodes, for this traversal order.
  1. If left link of node P is null, then this link is replaced by the address of its predecessor.
  2. If right link of node P is null, then it is replaced by the address of its successor.
• Node of Threaded Binary Tree
  • LTHREAD = true = Denotes leaf thread link
  • LTHREAD = false = Denotes leaf structural link
  • RTHREAD = true = Denotes right threaded link
  • RTHREAD = false = Denotes right structural link
• Head node is simply another node which serves as the predecessor and successor of first and last tree nodes. Tree is attached to the left branch of the head node

Fully In-threaded binary tree of given binary tree