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