Monday, May 11, 2020

Write a short note on threaded binary tree

  • 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.
    • If left link of node P is null, then this link is replaced by the address of its predecessor.
    • If right link of node P is null, then it is replaced by the address of its successor
  • Because the left or right link of a node can denote either structural link or a thread, we must somehow be able to distinguish them.
  • Method 1:- Represent thread a –ve address.
  • Method 2:- To have a separate Boolean flag for each of left and right pointers, node structure for this is given below,
Alternate node for 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
  • Inorder traversal is faster than unthreaded version as stack is not required.
  • Effectively determines the predecessor and successor for inorder traversal, for unthreaded tree this task is more difficult.
  • A stack is required to provide upward pointing information in tree which threading provides.
  • It is possible to generate successor or predecessor of any node without having over head of stack with the help of threading.

  • Threaded trees are unable to share common subtrees
  • If –ve addressing is not permitted in programming language, two additional fields are required.
  • Insertion into and deletion from threaded binary tree are more time consuming because both thread and structural link must be maintained.
To Get Fast Updates on Your Mobile, Join: WhatsApp Group | Telegram Channel
Important: Please always Check and Confirm the above details with the official Advertisement / Notification.

Follow by Email

Blog Archive


Follow Us

Contact Form1


Email *

Message *