text: Extract Leaves of a Binary Tree in a Doubly Linked List | C program to extract leaves of a Binary Tree in a Doubly Linked List ; Structure for tree and linked list ; Main function which extracts all leaves from given Binary Tree . The function returns new root of Binary Tree ( Note that root may changeif Binary Tree has only one node ) . The function also sets * head_ref as head of doubly linked list . left pointer of tree is used as prev in DLL and right pointer is used as next ; Utility function for allocating node for Binary Tree . ; Utility function for printing tree in In - Order . ; Utility function for printing double linked list . ; Driver program to test above function
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct Node { int data ; struct Node * left , * right ; } ; struct Node * extractLeafList ( struct Node * root , struct Node * * head_ref ) { if ( root == NULL ) return NULL ; if ( root -> left == NULL && root -> right == NULL ) { root -> right = * head_ref ; if ( * head_ref != NULL ) ( * head_ref ) -> left = root ; return NULL ; } root -> right = extractLeafList ( root -> right , head_ref ) ; root -> left = extractLeafList ( root -> left , head_ref ) ; return root ; } struct Node * newNode ( int data ) { struct Node * node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } void print ( struct Node * root ) { if ( root != NULL ) { print ( root -> left ) ; printf ( " % d ▁ " , root -> data ) ; print ( root -> right ) ; } } void printList ( struct Node * head ) { while ( head ) { printf ( " % d ▁ " , head -> data ) ; head = head -> right ; } } int main ( ) { struct Node * head = NULL ; struct Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> right = newNode ( 6 ) ; root -> left -> left -> left = newNode ( 7 ) ; root -> left -> left -> right = newNode ( 8 ) ; root -> right -> right -> left = newNode ( 9 ) ; root -> right -> right -> right = newNode ( 10 ) ; printf ( " Inorder ▁ Trvaersal ▁ of ▁ given ▁ Tree ▁ is : STRNEWLINE " ) ; print ( root ) ; root = extractLeafList ( root , & head ) ; printf ( " Extracted Double Linked list is : " printList ( head ) ; printf ( " Inorder traversal of modified tree is : " print ( root ) ; return 0 ; }