1.
Introduction
2.
Flattening BST
3.
Approach
4.
Efficient Approach
5.
5.1.
What does the Flattening BST means?
5.2.
How can we get the node values in sorted order in BST?
5.3.
What can be the best Space and Time Complexity achieved to solve the problem of Flattening BST in sorted order?
6.
Conclusion
Last Updated: Mar 27, 2024

# Flattening BST in Sorted List

## Introduction

In this article, we will cover the problem of Flattening BST in a sorted list. To be precise, the value of each node will be lesser than the values of nodes that are residing right to it. And the left of the leftmost node must be null. This blog will discuss the approach for Flattening BST using O(H) space where ‘H’ will be the height of the BST.

Also see, Data Structures

So, before jumping into the real problem let us first discuss what flattening in this context refers to.

## Flattening BST

‘Flattening’ in this context means is to convert the BST into a linear structure and that too in sorted order. You can relate this with converting a BST to a singly Linked List in which each node is connected to another with the help of a pointer.

Let’s understand this with the help of an example.

Consider the following BST

After Flattening this BST in sorted order the figure will look like this

Now let’s jump into the approach to understand this much better.

## 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

*/

/*

Printing Nodes

*/

return 0;

}``````

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;
}``````

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.

### 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.