# C++ program to find the median array for Binary tree

In 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`