bst to sorted array

1// C++ implementation of the approach
2#include <bits/stdc++.h>
3using namespace std;
4 
5// Node of the binary tree
6struct node {
7    int data;
8    node* left;
9    node* right;
10    node(int data)
11    {
12        this->data = data;
13        left = NULL;
14        right = NULL;
15    }
16};
17 
18// Function to print flattened
19// binary Tree
20void print(node* parent)
21{
22    node* curr = parent;
23    while (curr != NULL)
24        cout << curr->data << " ", curr = curr->right;
25}
26 
27// Function to perform in-order traversal
28// recursively
29void inorder(node* curr, node*& prev)
30{
31    // Base case
32    if (curr == NULL)
33        return;
34    inorder(curr->left, prev);
35    prev->left = NULL;
36    prev->right = curr;
37    prev = curr;
38    inorder(curr->right, prev);
39}
40 
41// Function to flatten binary tree using
42// level order traversal
43node* flatten(node* parent)
44{
45    // Dummy node
46    node* dummy = new node(-1);
47 
48    // Pointer to previous element
49    node* prev = dummy;
50 
51    // Calling in-order traversal
52    inorder(parent, prev);
53 
54    prev->left = NULL;
55    prev->right = NULL;
56    node* ret = dummy->right;
57 
58    // Delete dummy node
59    delete dummy;
60    return ret;
61}
62 
63// Driver code
64int main()
65{
66    node* root = new node(5);
67    root->left = new node(3);
68    root->right = new node(7);
69    root->left->left = new node(2);
70    root->left->right = new node(4);
71    root->right->left = new node(6);
72    root->right->right = new node(8);
73 
74    // Calling required function
75    print(flatten(root));
76 
77    return 0;
78}
79