Convert a Binary Tree to Threaded binary tree | Set 2 ( Efficient ) | 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 ; 1 / \ 2 3 / \ / \ 4 5 6 7
class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; this . isThreaded = false ; } } function createThreaded ( root ) { if ( root == null ) return null ; if ( root . left == null && root . right == null ) return root ; if ( root . left != null ) { var l = createThreaded ( root . left ) ; l . right = root ; l . isThreaded = true ; } if ( root . right == null ) return root ; return createThreaded ( root . right ) ; } function leftMost ( root ) { while ( root != null && root . left != null ) root = root . left ; return root ; } function inOrder ( root ) { if ( root == null ) return ; var cur = leftMost ( root ) ; while ( cur != null ) { document . write ( cur . key + " " ) ; if ( cur . isThreaded ) cur = cur . right ; else cur = leftMost ( cur . right ) ; } } function newNode ( key ) { var temp = new Node ( ) ; temp . left = temp . right = null ; temp . key = key ; return temp ; } var 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 ) ; document . write ( " " + " " ) ; inOrder ( root ) ;