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

Also, read

Leave a Reply

Your email address will not be published.