Binary Search Trees: Flatten BST to sorted list

Problem Statement:

You are given a root of a binary tree.

You need to flatten into a sorted list.

Solution

We need to do inorder traversal.

For that we will create a dummy node.

Then we take a pointer ‘prev’ and point it to dummy node.

Then we perform in-order traversal as:
	prev->right = curr
	prev->left = NULL
	prev = curr.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

void print_list(Node* parent)
{
    Node* curr = parent;
    while (curr != NULL)
    {
        cout << curr->data << " ";
        curr = curr->right;
     }
}

void inorder_convert(Node* curr, Node*& prev)
{
    if (curr == NULL)
        return;
    inorder_convert(curr->left, prev);
    prev->left = NULL;
    prev->right = curr;
    prev = curr;
    inorder_convert(curr->right, prev);
}

Node* flatten_BST_to_list(Node* parent)
{
    Node* dummy =  get_new_node(-1);
  
    Node* prev = dummy;
  
    inorder_convert(parent, prev);
  
    prev->left = NULL;
    prev->right = NULL;
    Node* ret = dummy->right;
  
    delete dummy;
    return ret;
}
 

int main()
{
    Node* root =   get_new_node(5);
    root->left =   get_new_node(3);
    root->right =   get_new_node(7);
    root->left->left =   get_new_node(2);
    root->left->right =   get_new_node(4);
    root->right->left =   get_new_node(6);
    root->right->right =   get_new_node(8);
  
    // Calling required function
    print_list(flatten_BST_to_list(root));

    return 0;
}

Output:

2 3 4 5 6 7 8