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 { int data ; Node left , right ; Node ( int item ) { data = item ; right = left = null ; } } public class BinaryTree { Node root ; Node head ; Node prev ; public Node extractLeafList ( Node 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 ; } void inorder ( Node node ) { if ( node == null ) return ; inorder ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; inorder ( node . right ) ; } public void printDLL ( Node head ) { Node last = null ; while ( head != null ) { System . out . print ( head . data + " ▁ " ) ; last = head ; head = head . right ; } } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . right = new Node ( 6 ) ; tree . root . left . left . left = new Node ( 7 ) ; tree . root . left . left . right = new Node ( 8 ) ; tree . root . right . right . left = new Node ( 9 ) ; tree . root . right . right . right = new Node ( 10 ) ; System . out . println ( " Inorder ▁ traversal ▁ of ▁ given ▁ tree ▁ is ▁ : ▁ " ) ; tree . inorder ( tree . root ) ; tree . extractLeafList ( tree . root ) ; System . out . println ( " " ) ; System . out . println ( " Extracted ▁ double ▁ link ▁ list ▁ is ▁ : ▁ " ) ; tree . printDLL ( tree . head ) ; System . out . println ( " " ) ; System . out . println ( " Inorder ▁ traversal ▁ of ▁ modified ▁ tree ▁ is ▁ : ▁ " ) ; tree . inorder ( tree . root ) ; } }