Extract Leaves of a Binary Tree in a Doubly Linked List | A binay tree node ; Binary Tree class ; The main function that links the list list to be traversed ; Utility function for printing tree in In - Order . ; Prints the DLL in both forward and reverse directions . ; Driver program to test above functions
class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } var root ; var head ; var prev ; function extractLeafList ( root ) { if ( root == null ) return null ; if ( root . left == null && root . right == null ) { if ( head == null ) { head = root ; prev = root ; } else { prev . right = root ; root . left = prev ; prev = root ; } return null ; } root . left = extractLeafList ( root . left ) ; root . right = extractLeafList ( root . right ) ; return root ; } function inorder ( node ) { if ( node == null ) return ; inorder ( node . left ) ; document . write ( node . data + " " ) ; inorder ( node . right ) ; } function printDLL ( head ) { var last = null ; while ( head != null ) { document . write ( head . data + " " ) ; last = head ; head = head . right ; } } root = new Node ( 1 ) ; root . left = new Node ( 2 ) ; root . right = new Node ( 3 ) ; root . left . left = new Node ( 4 ) ; root . left . right = new Node ( 5 ) ; root . right . right = new Node ( 6 ) ; root . left . left . left = new Node ( 7 ) ; root . left . left . right = new Node ( 8 ) ; root . right . right . left = new Node ( 9 ) ; root . right . right . right = new Node ( 10 ) ; document . write ( " " ) ; inorder ( root ) ; extractLeafList ( root ) ; document . write ( " " ) ; document . write ( " " ) ; printDLL ( head ) ; document . write ( " " ) ; document . write ( " " ) ; inorder ( root ) ;