Convert a Binary Tree to Threaded binary tree | Set 2 ( Efficient ) | C ++ program to convert a Binary Tree to Threaded Tree ; Structure of a node in threaded binary tree ; Used to indicate whether the right pointer is a normal right pointer or a pointer to inorder successor . ; Converts tree with given root to threaded binary tree . This function returns rightmost child of root . ; Base cases : Tree is empty or has single node ; Find predecessor if it exists ; Find predecessor of root ( Rightmost child in left subtree ) ; Link a thread from predecessor to root . ; If current node is rightmost child ; Recur for right subtree . ; A utility function to find leftmost node in a binary tree rooted with ' root ' . This function is used in inOrder ( ) ; Function to do inorder traversal of a threadded binary tree ; Find the leftmost node in Binary Tree ; If this Node is a thread Node , then go to inorder successor ; Else go to the leftmost child in right subtree ; A utility function to create a new node ; Driver program to test above functions ; 1 / \ 2 3 / \ / \ 4 5 6 7
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; Node * left , * right ; bool isThreaded ; } ; Node * createThreaded ( Node * root ) { if ( root == NULL ) return NULL ; if ( root -> left == NULL && root -> right == NULL ) return root ; if ( root -> left != NULL ) { Node * l = createThreaded ( root -> left ) ; l -> right = root ; l -> isThreaded = true ; } if ( root -> right == NULL ) return root ; return createThreaded ( root -> right ) ; } Node * leftMost ( Node * root ) { while ( root != NULL && root -> left != NULL ) root = root -> left ; return root ; } void inOrder ( Node * root ) { if ( root == NULL ) return ; Node * cur = leftMost ( root ) ; while ( cur != NULL ) { cout << cur -> key << " ▁ " ; if ( cur -> isThreaded ) cur = cur -> right ; else cur = leftMost ( cur -> right ) ; } } Node * newNode ( int key ) { Node * temp = new Node ; temp -> left = temp -> right = NULL ; temp -> key = key ; return temp ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; createThreaded ( root ) ; cout << " Inorder ▁ traversal ▁ of ▁ created ▁ " " threaded ▁ tree ▁ is STRNEWLINE " ; inOrder ( root ) ; return 0 ; }