{"id":27704,"date":"2018-04-09T20:22:49","date_gmt":"2018-04-09T14:52:49","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27704"},"modified":"2018-09-11T19:32:34","modified_gmt":"2018-09-11T14:02:34","slug":"threaded-binary-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/threaded-binary-tree\/","title":{"rendered":"Threaded Binary Tree"},"content":{"rendered":"

Inorder traversal of a Binary tree<\/a> is either be done using recursion or with the use of a auxiliary stack<\/a>.<\/span> The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the inorder successor of the node (if it exists).<\/p>\n

There are two types of threaded binary trees.
\nSingle Threaded: <\/strong><\/em>Where a NULL right pointers is made to point to the inorder successor (if successor exists)<\/p>\n

Double Threaded:<\/strong><\/em> Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.<\/p>\n

The threads are also useful for fast accessing ancestors of a node.<\/p>\n

Following diagram shows an example Single Threaded Binary Tree. The dotted lines represent threads.
\n\"threadedBT\"<\/a><\/p>\n

C representation of a Threaded Node<\/strong>
\nFollowing is C representation of a single threaded node.<\/p>\n

\n
\n\n\n\n
\n
\n
struct<\/code> Node <\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>int<\/code> data;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>Node *left, *right;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>bool<\/code> rightThread;\u00a0 <\/code><\/div>\n
}<\/code><\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n

Since right pointer is used for two purposes, the boolean variable rightThread is used to indicate whether right pointer points to right child or inorder successor. Similarly, we can add leftThread for a double threaded binary tree.<\/p>\n

Inorder Taversal using Threads<\/strong>
\nFollowing is C code for inorder traversal in a threaded binary tree.<\/p>\n

<\/div> 
\/\/ Utility function to find leftmost node in atree rooted with nstruct Node* leftMost(struct Node *n){    if (n == NULL)       return NULL;     while (n->left != NULL)        n = n->left;     return n;} \/\/ C code to do inorder traversal in a threadded binary treevoid inOrder(struct Node *root){    struct Node *cur = leftmost(root);    while (cur != NULL)    {        printf("%d ", cur->data);         \/\/ If this node is a thread node, then go to        \/\/ inorder successor        if (cur->rightThread)            cur = cur->right;        else \/\/ Else go to the leftmost child in right subtree            cur = leftmost(cur->right);    }}<\/code><\/pre> <\/div>\n","protected":false},"excerpt":{"rendered":"
Threaded Binary Tree – learn in 30 secfrom microsoft awarded MVP,Inorder traversal of a Binary tree is either be done using recursion or with the use of a auxiliary stack. <\/p>\n","protected":false},"author":1,"featured_media":31262,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80125,80140],"tags":[82006,82010,82005,82007,82003,82008,82009,82004],"class_list":["post-27704","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binary-tree","category-binay-tree","tag-advantages-of-threaded-binary-tree","tag-pre-order-threaded-binary-tree","tag-threaded-binary-tree-geeksforgeeks","tag-threaded-binary-tree-in-data-structure-notes","tag-threaded-binary-tree-in-data-structure-pdf","tag-threaded-binary-tree-insertion","tag-threaded-binary-tree-ppt","tag-threaded-binary-tree-tutorial-point"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27704","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27704"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27704\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31262"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27704"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27704"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27704"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}