Extract Leaves of a Binary Tree in a Doubly Linked List

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place. Assume that the node structure of DLL and Binary Tree is same, only the meaning of left and right pointers are different. In DLL, left means previous pointer and right means next pointer [Check here for the details].

Let the following be input binary tree
        1
     /     \
    2       3
   / \       \
  4   5       6
 / \         / \
7   8       9   10 

Output:
Doubly Linked List
7<->8<->5<->9<->10

Modified Tree:
        1
     /     \
    2       3
   /         \
  4           6

Solution: we travel the tree in the order of right subtree, current node, and left subtree; thus, the order of leaves we travel are 10, 9, 5, 8, 7. Each time a leaf is encountered, we add it to the beginning of the DLL (this is also why we travel the tree in the order of right subtree, current node, and left subtree).

#include<iostream>

using std::cout;
using std::endl;

//Structure for tree and linked list 
typedef struct node{
    int data;
    struct node *left, *right;
}* Node;

//Create a node and return its addr
Node createNode(int data){
    Node newNode = new struct node;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//Extract leaves of binary tree to a DLL
void extractLeafList(Node &root, Node &head){
    if(!root) return;
    if(!root->left && !root->right){
        if(head!=NULL){
            root->right = head;
            head->left = root;
        }
        head = root;
        root = NULL;
        return;
    }
    extractLeafList(root->right, head);
    extractLeafList(root->left, head);
}

//Print the binary tree in In-order
void printTree(Node root){
    if(!root) return;
    printTree(root->left);
    cout << root->data << " ";
    printTree(root->right);
}

//Print DLL 
void printDLL(Node head){
    while(head!=NULL){
        cout << head->data << " ";
        head = head->right;
    }
    cout<<endl;
}

int main(){
    //Create a binary tree
    Node head = NULL;
    Node root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    root->left->left->left = createNode(7);
    root->left->left->right = createNode(8);
    root->right->right->left = createNode(9);
    root->right->right->right = createNode(10);

    cout<<"Inorder Trvaersal of given Tree is:"<<endl;
    printTree(root);
    cout<<endl;

    extractLeafList(root, head);

    cout<<"Extracted Double Linked list is:"<<endl;
    printDLL(head);

    cout<<"Inorder traversal of modified tree is:"<<endl;
    printTree(root);
    cout<<endl;
    return 0;
}