Threaded Binary Tree


Why threaded binary trees?

We don’t need to use recursion or any external stack for traversals of tree which is time consuming.


Drawbacks

Size of node structure of tree increases.


Types of TBT


1.  Single threaded

       a)Left threaded (LTBT)
          Left link of node without a left child points to its inorder predecessor.
          Left-threaded-binary-tree
          
      b)Right threaded (RTBT)
         Right link of any node without a right child points to its inorder successor.
             Right-threaded-binary-tree                                                                                                                                                           

2.  Double threaded

Left link of node without a left child points to its inorder predecessor and Right link of any node without a right child points to its inorder successor.
So it is both left threaded and right threaded.

Double-threaded-binary-tree




More


1 comment:

Subscribe to: Posts (Atom)