Create a wave array from the given Binary Search Tree
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 tree struct 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 Array void 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 Code int 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 approach import java.util.*; class GFG{ // Node of the Binary Search tree static 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 Array static 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 Code public 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 tree class Node: def __init__( self , data): self .data = data; self .right = None ; self .left = None ; # Function to convert Binary Search # Tree into a wave Array def 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 Code if __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 approach using System; using System.Collections.Generic; public class GFG{ // Node of the Binary Search tree public 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 Array static 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 Code public 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> |
4 2 8 6 12 10 14
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us