Do you think IIT Guwahati certified course can help you in your career?
Introduction
You said coding interview. I heard BST. Yes, BST is the most asked topic when it comes to coding interviews, and thus, having a strong grasp over it surely helps us to give an edge over our competition. Ninja is here to help you strengthen the topic of BST, and today we are going to discuss the problem ‘Flatten a Binary Search Tree to convert the tree into a wave list in place only’. Now let’s look at the problem statement.
We have been given a Binary Search Tree. Our task is to flatten this binary search tree into a wave list. Now a wave list is an array in which
ARRAY[0] > = ARRAY[1] < = ARRAY[2] > = ARRAY[3] and so on.
Here we don’t have to return an array but a binary tree in this form (Wave List).
Let’s understand this better by the following example:
Let’s say that the BST given to us looks like this:
Then our output will be
Explanation
Here we can see that this tree is in the form of a wave 4 > 24 < 8 > 10.
Intuition
Now we know that Inorder Traversal of a BST gives us nodes in sorted order (increasing order); thus, we can make use of it. The intuition is simple we will store in order traversal of first N/2 nodes using a stack, let’s say ‘FIRST_HALF’ and will store and reverse the inorder traversal of last N/2 nodes using the stack lets say ‘SECOND_HALF’. Now we will populate the right pointer of these nodes from the nodes in the stack, and the left pointer of all nodes will be set to NULL (evident from the output image above). The populating step will become more evident by the code.
The code is given below.
Code
#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
// Tree Node Class.
class TreeNode
{
public:
int data;
TreeNode * right;
TreeNode * left;
// Constructor
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Insert function of BST.
TreeNode* insert(int data, TreeNode *node)
{
if (node == NULL)
{
TreeNode *newNode = new TreeNode(data);
return newNode;
}
if (data < node->data)
{
node->left = insert(data, node->left);
}
else
{
node->right = insert(data, node->right);
}
return node;
}
// Main function where the magic happens.
TreeNode* wave(TreeNode *root, int count)
{
// For inorder traversal of N/2 nodes.
stack<TreeNode*> firstHalf;
// For reverse inorder traversal of remaining N/2 nodes.
stack<TreeNode*> secondHalf;
TreeNode *firstHalfroot = root;
TreeNode *secondHalfRoot = root;
TreeNode *firstHalfcurr = NULL;
TreeNode *secondHalfcurr = NULL;
// Head of final tree.
TreeNode *finalhead = NULL;
TreeNode *temp = NULL;
int l = 0;
int half = ceil(count / 2.0);
for (int l = 0; l < half; l++)
{
// Iterative inorder traversal
while (firstHalfroot != NULL)
{
firstHalf.push(firstHalfroot);
firstHalfroot = firstHalfroot->left;
}
firstHalfcurr = firstHalf.top();
firstHalf.pop();
firstHalfroot = firstHalfcurr->right;
// Iterative reverse inorder traversal
while (secondHalfRoot != NULL)
{
secondHalf.push(secondHalfRoot);
secondHalfRoot = secondHalfRoot->right;
}
secondHalfcurr = secondHalf.top();
secondHalf.pop();
secondHalfRoot = secondHalfcurr->left;
// If both points to the same value then we will store only one.
if (firstHalfcurr->data == secondHalfcurr->data)
{
temp->right = firstHalfcurr;
temp = temp->right;
break;
}
// If it’s the first node, i.e., ‘FINALHEAD’ is NULL.
if (finalhead == NULL)
{
finalhead = firstHalfcurr;
temp = firstHalfcurr;
temp->right = secondHalfcurr;
temp = temp->right;
}
else
{
temp->right = firstHalfcurr;
temp = temp->right;
temp->right = secondHalfcurr;
temp = temp->right;
}
}
temp->right = NULL;
// Left pointers will be set to NULL.
temp = finalhead;
while (temp != NULL)
{
temp->left = NULL;
temp = temp->right;
}
return finalhead;
}
// Main function
int main()
{
TreeNode *root = NULL;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
root = insert(x, root);
}
// Function Call
TreeNode *head = wave(root, n);
while (head)
{
cout << head->data << " ";
head = head->right;
}
return 0;
}
You can also try this code with Online C++ Compiler
We begin by looking at the root node. If the tree is null, it means that the key we're looking for does not exist in the tree. Otherwise, the key is compared to the root node; if they match, the node is returned; check for its left subtree if key < root, and check recursively for the left subtree. If that is not the case, look for the right subtree by using if key > root and then search for the right subtree recursively.
What is the degree in a binary tree?
The degree of a binary tree is the total number of nodes that it has as offspring, i.e., the total number of nodes that originate from it. Because the tree's leaf has no children, its degree is zero. The number of partitions in the subtree with that node as the root determines a node's degree.
What is the range sum of BST?
The range sum of BST or any other tree is nothing but the sum between the provided intervals.
What characteristics does a binary search tree have?
A node's left subtree only contains nodes with keys lower than the node's key.
A node's right subtree only contains nodes with keys larger than the node's key.
Each subtree on the left and right must be a binary search tree.
Conclusion
We saw how we could solve the problem by using the in-order traversal. Solving a tough problem always increases one’s confidence but hold on.
There are a lot more topics and a variety of questions in BST. But you don’t have to worry about that. Ninja is always here for you. So, Move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!
85+ registered