Given a Binary Search Tree, the task is to create a wave array from the given Binary Search Tree. An array arr[0..n-1] is called a wave array if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …
Examples:
Input:
Output: 4 2 8 6 12 10 14
Explanation: The above mentioned array {4, 2, 8, 6, 12, 10, 14} is one of the many valid wave arrays.Input:
Output: 4 2 8 6 12
Approach: The given problem can be solved by the observation that the Inorder Traversal of the Binary Search Tree gives nodes in non-decreasing order. Therefore, store the inorder traversal of the given tree into a vector. Since the vector contains elements in sorted order, it can be converted into a wave array by swapping the adjacent elements for all elements in the range [0, N) using the approach discussed in this article.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Node of the Binary Search treestruct Node { int data; Node* right; Node* left; // Constructor Node(int data) { this->data = data; this->left = NULL; this->right = NULL; }};// Function to convert Binary Search// Tree into a wave Arrayvoid toWaveArray(Node* root){ // Stores the final wave array vector<int> waveArr; stack<Node*> s; Node* curr = root; // Perform the Inorder traversal // of the given BST while (curr != NULL || s.empty() == false) { // Reach the left most Node of // the curr Node while (curr != NULL) { // Place pointer to a tree node // in stack before traversing // the node's left subtree s.push(curr); curr = curr->left; } curr = s.top(); s.pop(); // Insert into wave array waveArr.push_back(curr->data); // Visit the right subtree curr = curr->right; } // Convert sorted array into wave array for (int i = 0; i + 1 < waveArr.size(); i += 2) { swap(waveArr[i], waveArr[i + 1]); } // Print the answer for (int i = 0; i < waveArr.size(); i++) { cout << waveArr[i] << " "; }}// Driver Codeint main(){ Node* root = new Node(8); root->left = new Node(4); root->right = new Node(12); root->right->left = new Node(10); root->right->right = new Node(14); root->left->left = new Node(2); root->left->right = new Node(6); toWaveArray(root); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Node of the Binary Search treestatic class Node { int data; Node right; Node left; // Constructor Node(int data) { this.data = data; this.left = null; this.right = null; }};// Function to convert Binary Search// Tree into a wave Arraystatic void toWaveArray(Node root){ // Stores the final wave array Vector<Integer> waveArr = new Vector<>(); Stack<Node> s = new Stack<>(); Node curr = root; // Perform the Inorder traversal // of the given BST while (curr != null || s.isEmpty() == false) { // Reach the left most Node of // the curr Node while (curr != null) { // Place pointer to a tree node // in stack before traversing // the node's left subtree s.add(curr); curr = curr.left; } curr = s.peek(); s.pop(); // Insert into wave array waveArr.add(curr.data); // Visit the right subtree curr = curr.right; } // Convert sorted array into wave array for (int i = 0; i + 1 < waveArr.size(); i += 2) { int t = waveArr.get(i); waveArr.set(i, waveArr.get(i+1)); waveArr.set(i+1, t); } // Print the answer for (int i = 0; i < waveArr.size(); i++) { System.out.print(waveArr.get(i)+ " "); }}// Driver Codepublic static void main(String[] args){ Node root = new Node(8); root.left = new Node(4); root.right = new Node(12); root.right.left = new Node(10); root.right.right = new Node(14); root.left.left = new Node(2); root.left.right = new Node(6); toWaveArray(root);}}// This code is contributed by umadevi9616 |
Python3
# Python program for the above approach# Node of the Binary Search treeclass Node: def __init__(self, data): self.data = data; self.right = None; self.left = None; # Function to convert Binary Search# Tree into a wave Arraydef toWaveArray(root): # Stores the final wave array waveArr = []; s = []; curr = root; # Perform the Inorder traversal # of the given BST while (curr != None or len(s) != 0): # Reach the left most Node of # the curr Node while (curr != None): # Place pointer to a tree Node # in stack before traversing # the Node's left subtree s.append(curr); curr = curr.left; curr = s.pop(); # Insert into wave array waveArr.append(curr.data); # Visit the right subtree curr = curr.right; # Convert sorted array into wave array for i in range(0,len(waveArr)-1, 2): t = waveArr[i]; waveArr[i] = waveArr[i + 1]; waveArr[i + 1]= t; # Print the answer for i in range(len(waveArr)): print(waveArr[i], end=" ");# Driver Codeif __name__ == '__main__': root = Node(8); root.left = Node(4); root.right = Node(12); root.right.left = Node(10); root.right.right = Node(14); root.left.left = Node(2); root.left.right = Node(6); toWaveArray(root);# This code is contributed by Rajput-Ji |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Node of the Binary Search treepublic class Node { public int data; public Node right; public Node left; // Constructor public Node(int data) { this.data = data; this.left = null; this.right = null; }};// Function to convert Binary Search// Tree into a wave Arraystatic void toWaveArray(Node root){ // Stores the readonly wave array List<int> waveArr = new List<int>(); Stack<Node> s = new Stack<Node>(); Node curr = root; // Perform the Inorder traversal // of the given BST while (curr != null || s.Count!=0 ) { // Reach the left most Node of // the curr Node while (curr != null) { // Place pointer to a tree node // in stack before traversing // the node's left subtree s.Push(curr); curr = curr.left; } curr = s.Peek(); s.Pop(); // Insert into wave array waveArr.Add(curr.data); // Visit the right subtree curr = curr.right; } // Convert sorted array into wave array for (int i = 0; i + 1 < waveArr.Count; i += 2) { int t = waveArr[i]; waveArr[i]= waveArr[i+1]; waveArr[i+1]= t; } // Print the answer for (int i = 0; i < waveArr.Count; i++) { Console.Write(waveArr[i]+ " "); }}// Driver Codepublic static void Main(String[] args){ Node root = new Node(8); root.left = new Node(4); root.right = new Node(12); root.right.left = new Node(10); root.right.right = new Node(14); root.left.left = new Node(2); root.left.right = new Node(6); toWaveArray(root);}}// This code is contributed by umadevi9616 |
Javascript
<script> // JavaScript Program to implement // the above approach class Node { constructor(data) { this.data = data; this.left = this.right = null; } } // Function to convert Binary Search // Tree into a wave Array function toWaveArray(root) { // Stores the final wave array let waveArr = []; let s = []; let curr = root; // Perform the Inorder traversal // of the given BST while (curr != null || s.length != 0) { // Reach the left most Node of // the curr Node while (curr != null) { // Place pointer to a tree node // in stack before traversing // the node's left subtree s.push(curr); curr = curr.left; } curr = s[s.length - 1]; s.pop(); // Insert into wave array waveArr.push(curr.data); // Visit the right subtree curr = curr.right; } // Convert sorted array into wave array for (let i = 0; i + 1 < waveArr.length; i += 2) { let temp = waveArr[i] waveArr[i] = waveArr[i + 1] waveArr[i + 1] = temp } // Print the answer for (let i = 0; i < waveArr.length; i++) { document.write(waveArr[i] + " "); } } // Driver Code let root = new Node(8); root.left = new Node(4); root.right = new Node(12); root.right.left = new Node(10); root.right.right = new Node(14); root.left.left = new Node(2); root.left.right = new Node(6); toWaveArray(root); // This code is contributed by Potta Lokesh </script> |
Output:
4 2 8 6 12 10 14
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
