C++ program to find the median array for Binary tree
By Abinash ReddyIn this article, we will learn how to find the median array for a Binary tree in C++. A median array is an array that formed with help of Inorder, Preorder, Postorder traversal of the binary tree i.e.
median_arr[i] = median(inorder[i], postorder[i], preorder[i])
Example
Input: 8
/ \
1 4
/ \ / \
5 6 5 6
Output: 5 1 5 6 5 4 6
Explanation:
Preorder traversal is: {8, 1, 5, 6, 4, 5, 6,}
Inorder traversal is: {5, 1, 6, 8, 5, 4, 6}
Postorder traversal is: {5, 6, 1, 5, 6, 4, 8}
median_arr[0] = median(8, 5, 5) = 5
median_arr[1] = median(1, 1, 6) = 1
median_arr[2] = median(5, 6, 1) = 5
median_arr[3] = median(6, 8, 5) = 6
median_arr[4] = median(4, 5, 6) = 5
median_arr[5] = median(4, 5, 4) = 4
median_arr[6] = median(8, 6, 6) = 6
Median array for Binary tree in C++
1. Create a median_arr vector to store the result.
2. Firstly Declare three vectors and find the preorder, inorder, postorder traversal of the given BST and store them in vector.
3. Create a temporary vector, from o to n store insert values at the position in each traverse into the temporary vector.
4. Sort the temporary vector and the mid element into the median_arr vector.
5. Finally, print the median_arr vector.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// function to generate the post order traversal
void Postorder(Node* node, vector<int>& postorder)
{
if (node == NULL)
return;
Postorder(node->left, postorder);
Postorder(node->right, postorder);
postorder.push_back(node->data);
}
// function to generate the inorder traversal
void Inorder(Node* node, vector<int>& inorder)
{
if (node == NULL)
return;
Inorder(node->left, inorder);
inorder.push_back(node->data);
Inorder(node->right, inorder);
}
// function to generate the preorder traversal
void Preorder(Node* node, vector<int>& preorder)
{
if (node == NULL)
return;
preorder.push_back(node->data);
Preorder(node->left, preorder);
Preorder(node->right, preorder);
}
// function to print the vector
void printArray(vector<int> median_arr)
{
for (int i = 0; i < median_arr.size(); i++)
cout << median_arr[i] << " ";
return;
}
// function to calculate the meadian array
void medianArray(Node* node)
{
// vector to store the result
vector<int> median_arr;
if (node == NULL)
return;
// vector to store the traversals
vector<int> preorder, postorder, inorder;
Postorder(node, postorder);
Inorder(node, inorder);
Preorder(node, preorder);
int n = inorder.size();
for (int i = 0; i < n; i++) {
vector<int> temp;
temp.push_back(postorder[i]);
temp.push_back(inorder[i]);
temp.push_back(preorder[i]);
sort(temp.begin(), temp.end());
median_arr.push_back(temp[1]);
}
printArray(median_arr);
return;
}
int main()
{
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
medianArray(root);
return 0;
}
Output
4 2 4 5 6 3 7
Also, read
Leave a Reply