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 code
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int data ; Node * left , * right ; } ; Node * extractLeafList ( Node * root , 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 ; * head_ref = root ; return NULL ; } root -> right = extractLeafList ( root -> right , head_ref ) ; root -> left = extractLeafList ( root -> left , head_ref ) ; return root ; } Node * newNode ( int data ) { Node * node = new Node ( ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } void print ( Node * root ) { if ( root != NULL ) { print ( root -> left ) ; cout << root -> data << " ▁ " ; print ( root -> right ) ; } } void printList ( Node * head ) { while ( head ) { cout << head -> data << " ▁ " ; head = head -> right ; } } int main ( ) { Node * head = NULL ; 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 ) ; cout << " Inorder ▁ Trvaersal ▁ of ▁ given ▁ Tree ▁ is : STRNEWLINE " ; print ( root ) ; root = extractLeafList ( root , & head ) ; cout << " Extracted Double Linked list is : " ; printList ( head ) ; cout << " Inorder traversal of modified tree is : " print ( root ) ; return 0 ; }