Approach
The first approach that comes into our mind is to store the values of BST in an array from the inorder traversal of the given BST. Then we create a new node for each element in the array, make its left child NULL and right child equal to the node containing the next element in the array. For the last element, we make both the left and right child NULL.
#include<bits/stdc++.h>
using namespace std;
/*
Created a binary search tree as
as Node having data, the pointer to left
and a pointer to the the right child a
*/
struct Node
{
int data;
struct Node* left, *right;
};
/*
Function to create a new Node
in BST
*/
struct Node *newNode(int value)
{
struct Node *temp = new Node;
temp -> data = value;
temp -> left = temp -> right = NULL;
return temp;
}
/*
Function to insert a new node with
given key in BST
*/
struct Node* insert(struct Node* node, int value)
{
/*
If the tree is empty
return the new node with the key
*/
if (node == NULL)
{
return newNode(value);
}
/*
If the the a key is less than particular
node data, then call recursion on left
else recur on right
*/
if (value < node -> data)
{
node -> left = insert(node -> left, value);
}
else if (value > node -> data)
{
node -> right = insert(node -> right, value);
}
// Return the node
return node;
}
void inorder(Node *root, vector<int> &inorderArray)
{
if (root == NULL)
{
return;
}
// Recur for left sub-tree
inorder(root->left, inorderArray);
// Add current node data to array
inorderArray.push_back(root->data);
// Recur for right sub-tree
inorder(root->right, inorderArray);
}
Node* flatten(Node* root)
{
if (root == NULL)
{
return root;
}
// Array to store inorder traversal
vector<int> inorderArray;
inorder(root, inorderArray);
// Create a pointer called newRoot, and store the first value of the array in it.
Node *newRoot = newNode(inorderArray[0]);
// Create a pointer called curr and store the newRoot in it.
Node *curr = newRoot;
for (int i = 1; i < inorderArray.size(); i++)
{
// Create a new node.
Node *temp = newNode(inorderArray[i]);
// Make the left child of curr as NULL and right child as the temp. And make curr = temp.
curr->left = NULL;
curr->right = temp;
curr = temp;
}
// Make both the left and the right child of the last node as NULL.
curr->left = NULL;
curr->right = NULL;
return newRoot;
}
// Function to print nodes of BST
void print(Node* root)
{
if(!root)
return;
print(root->left);
cout<<root->data<<" ";
print(root->right);
}
// main Function
int main()
{
/*
Let us create the following BST
6
/ \
3 8
/ \ / \
1 47 9
*/
/*
Inserting the values
for creating tree
*/
struct Node *head = NULL;
head = insert(head, 6);
insert(head, 3);
insert(head, 8);
insert(head, 1);
insert(head, 4);
insert(head, 7);
insert(head, 9);
/*
Printing Nodes
*/
print(head);
return 0;
}
You can also try this code with Online C++ Compiler
Output:
1 3 4 6 7 8 9
Time Complexity: The Time Complexity is O(N), where ‘N’ is the number of nodes in the given BST
We are traversing the BST only once to store all the values in the array after the inorder traversal. Then, we traverse the array one more time to create the flattened list. Hence, the overall time complexity is O(N).
Space Complexity: O(N), where ‘N’ is the total number of nodes in the given BST.
We are storing the values of all the nodes in an array after the inorder traversal. Hence, the overall space complexity will be O(N).
Efficient Approach
We can improve our previous approach in terms of space. To improve upon that we will use the inorder traversal of a binary tree as follows:
- We will first create a dummy node.
- Then we will create a variable, say ‘prev’ which will store the value of the previous node. Initially, we will make it to the dummy node.
-
Then at each step of the inorder traversal of the tree, we will perform the following operations:
- We will first set the prev->right = curr (where ‘curr’ refers to the current node)
- Setting prev->left = NULL (as we are flattering the given tree so to attain this we will have to connect the nodes with only one of the two pointers present in the node’s structure).
- Then we will make curr = curr->right.
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function to print the required flattened BST
void print(node* prev)
{
node* curr = prev;
while (curr != NULL)
{
cout << curr->data << " ";
curr = curr->right;
}
}
// Function for inorder traversal
void inorder(node* curr, node*& prev)
{
// Base case
if (curr == NULL)
{
return;
}
// Traversing left subtree
inorder(curr->left, prev);
// Flattening operations
prev->left = NULL;
prev->right = curr;
prev = curr;
// Traversing right subtree
inorder(curr->right, prev);
}
// Function to flatten BST
node* flattenBst(node* parent)
{
node* dummy = new node(-1);
// Pointer to previous node
node* prev = dummy;
// in-order traversal
inorder(parent, prev);
prev->left = NULL;
prev->right = NULL;
node* rt = dummy->right;
// Deleting dummy node
delete dummy;
return rt;
}
// Main Function
int main()
{
node* root = new node(6);
root->left = new node(3);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
root->right->left = new node(7);
root->right->right = new node(9);
print(flattenBst(root));
return 0;
}
You can also try this code with Online C++ Compiler
Output:
1 3 4 6 7 8 9
Time Complexity: O(N), where ‘N’ is the number of nodes in the given BST.
We are traversing the BST only once for the inorder traversal. Hence, the overall time complexity is O(N).
Space Complexity: O(H), where ‘H’ is the height of the given BST.
Here we are not using an array to store all the nodes of BST instead we are taking the help of the dummy node to flatten the BST which will make its space complexity O(H) in the worst case.
You can also read about insertion into bst.
Frequently Asked Questions
What does the Flattening BST means?
Flattening BST means converting the pyramid-shaped BST into a linear data structure. This can be done by converting the BST into a skewed shape or by converting it into a singly linked list.
How can we get the node values in sorted order in BST?
We can achieve this by doing inorder traversal of BST as the left subtree in BST contains the nodes with values lesser than that of the root node and the right subtree contains the nodes with values greater than that of the root node.
What can be the best Space and Time Complexity achieved to solve the problem of Flattening BST in sorted order?
The Time Complexity achieved from the efficient approach can be O(N) for all cases and Space Complexity achieved from the efficient approach can be O(H) (where ‘H’ is the height of the BST) even for the worst case.
Conclusion
In this article, we discussed the problem of Flattening BST in sorted order. We also discussed the approaches to solving the problem along with the discussion on their time and space complexities.
Recommended Reading:
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!
85+ registered