Do you think IIT Guwahati certified course can help you in your career?
Introduction
Arrays and trees (including binary trees, binary search trees, AVL trees, etc.) have been among the most common topics asked in interviews and form the basis of several programming problems.
This article will discuss one such problem to create a wave array from the given Binary Search Tree.
What is a wave array?
In this article’s context, a wave array is defined as an array where the first element is larger, the second element is smaller, the third element is larger again, and so on, creating a repeating wave-like pattern of alternating larger and smaller values.
So, without further ado, let’s jump into the problem statement.
Problem statement
The task is to convert a given Binary Search Tree into a wave array.
Note: Here, a wave array is an array arr[], where arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …
Example
Input
Output
12 6 24 23 26
Explanation
Here, We can see that the first element is larger than the second element, the second element is smaller than the third element, and so on. We have the larger-smaller-larger pattern (which represents a wave) as given in the definition of wave array. There can be multiple answers for a given BST.
Approach
Before moving on to solve this problem, we must brush up on a critical concept that we will be using to solve this problem.
We know that to traverse a binary search tree, we have the following three types of traversals, and each traversal has its advantage.
Inorder Traversal
Preorder Traversal
Postorder Traversal
In this problem, we will use inorder traversal to provide us with the nodes in an increasing order, which we will use to create a wave array.
Let’s see the algorithm step-by-step:
Algorithm
Create an empty list.
Store the inorder traversal of the given binary search tree into the list. (We can do inorder traversal both iteratively or recursively)
Swap every adjacent pair of nodes in the traversal sequence starting from the root node. If the number of nodes is odd, Ignore the last node.
The obtained array is the required wave array.
Dry Run
Code
// C++ program to create wave array from given BST
#include <bits/stdc++.h>
using namespace std;
// Node of Binary Search Tree
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
/*
Function to get inorder traversal of the binary tree.
It is known that the inorder traversal of a BST gives a sorted array.
*/
void inorder(TreeNode *root, vector<int> &inorderTraversal) {
if (root) {
inorder(root->left, inorderTraversal);
inorderTraversal.push_back(root->val);
inorder(root->right, inorderTraversal);
}
}
vector<int> BSTtoWaveArray(TreeNode *root) {
// Get sorted inorder traversal of given BST
vector<int> temp;
inorder(root, temp);
int n = int(temp.size());
// Converting sorted array to wave array by swapping adjacent elements
for (int i = 0; i + 1 < n; i += 2) {
swap(temp[i], temp[i + 1]);
}
// Returning the obtained wave array
return temp;
}
int main() {
// Given BST
TreeNode *root = new TreeNode(24);
root->left = new TreeNode(12);
root->right = new TreeNode(26);
root->left->left = new TreeNode(6);
root->left->right = new TreeNode(23);
// Printing the wave array
vector<int> waveArray = BSTtoWaveArray(root);
for (int &element : waveArray) {
cout << element << ' ';
}
cout << endl;
}
You can also try this code with Online C++ Compiler
The algorithm’s time complexity is O(n), where n is the number of nodes in the given Binary Search Tree. The time complexity to perform an inorder traversal is O(n) as we visit each one of the n nodes only once.
Space Complexity
The algorithm’s space complexity is O(n), where n is the number of nodes in the given Binary Search Tree. We keep track of all the nodes and store them in a vector of size n, so it occupies space of the order of n.
Frequently Asked Questions
What is a Binary Search tree?
A binary search tree is a tree data structure where each node has at most two children, and the value of every node in the left subtree is less than the value of its parent node, while the value of every node in the right subtree is greater than the value of its parent node.
What is a wave array?
A wave array is defined as an array where the first element is larger, the second element is smaller than the first one, the third element is larger than the second one, and so on, creating a repeating wave-like pattern of alternating larger and smaller values.
Is it possible to convert any Binary Tree to a wave array using this algorithm?
No, because this algorithm uses a property of Binary Search Trees, that their inorder traversal gives a sorted array.
Why does the inorder traversal of a Binary Search Tree give a sorted array?
The inorder traversal of a binary search tree gives a sorted array because of the nature of the binary search tree data structure itself, i.e., the values of nodes in the left subtree of a node are less than the node’s value, and the values of nodes in the right subtree of a node are greater than the node’s value.
When inorder traversal is performed, we first visit all the nodes in the left subtree, the root node, and then the nodes in the right subtree. This results in a sorted array.
How do you determine if two BSTs are equal?
Identical BSTs have the same structure, the same values for each node, and the same key-value pairs.
Conclusion
This blog discussed how we can create a wave array from the given Binary Search Tree.
To learn more, go to Coding Ninjas Studio to practice problems on various topics and ace your interviews like a Ninja! Practicing a bunch of questions is not enough in this competitive world. So check out where you stand among your peers by taking our mock tests and see which areas need improvement.
27+ registered 
