BST to DLL, C++ (gcc)

BST to DLL

#include <iostream>
#include <list>
#include <vector>
using namespace std;

struct BinTree {
  
    int data;
    BinTree *left;
    BinTree *right;
    
    BinTree(int d, BinTree* l, BinTree* r): data(d), left(l), right(r) {}
};

void BSTtoDLL(BinTree* node, BinTree*& head, BinTree*& tail){
        
    if(!node)
        return;

/* Go to left most child */
    if(node->left)
        BSTtoDLL(node->left, head, tail);

/* If this wasn't the first node being added to list*/  
    if(tail != NULL)
        tail->right = node;
    else
        head = node; 
       
     
    /* make left pointer point to last node, and update the 
       last node to current*/
    node->left = tail;
    tail = node;

/* If there is right child, process right child */
    if(node->right)
        BSTtoDLL(node->right, head, tail);

}

void printList(BinTree *root) {
    
    while (root) {
     
        cout << root->data << " ";
        root = root->right;
        
    }
    cout << endl;
}

//           4
//         /   \
//        2     8   
//       / \   / \   
//      1  3  6   9
//           / \
//          5   7   
//             
//

int main()
{

BinTree *h = new BinTree(7, NULL, NULL);
    BinTree *j = new BinTree(5, NULL, NULL);
    BinTree *g = new BinTree(9, NULL, NULL);
    BinTree *f = new BinTree(6, j, h);
    BinTree *e = new BinTree(3, NULL, NULL);
    BinTree *d = new BinTree(1, NULL, NULL);
    BinTree *c = new BinTree(8, f, g);
    BinTree *b = new BinTree(2, d, e);
    BinTree *a = new BinTree(4, b, c);

BinTree *head = NULL;
    BinTree *tail = NULL;
    
    BSTtoDLL(a, head, tail);
    printList(head);
    
}


run \| edit \| history \| help	0