Data Modelling & AI Data Structure & Algorithm

Find the median array for Binary tree

23 June 2025

0

Prerequisite: Tree Traversals (Inorder, Preorder and Postorder), Median
Given a Binary tree having integral nodes, the task is to find the median for each position in the preorder, postorder and inorder traversal of the tree.

The median array is given as the array formed with the help of PreOrder, PostOrder, and Inorder traversal of a tree, such that
med[i] = median(preorder[i], inorder[i], postorder[i])

Examples:

Input: Tree =
               1
             /   \
            2     3
          /  \
         4    5 
Output: {4, 2, 4, 3, 3}
Explanation:
Preorder traversal = {1 2 4 5 3}
Inorder traversal =  {4 2 5 1 3}
Postorder traversal = {4 5 2 3 1}
median[0] = median(1, 4, 4) = 4
median[1] = median(2, 2, 5) = 2
median[2] = median(4, 5, 2) = 4
median[3] = median(5, 1, 3) = 3
median[4] = median(3, 3, 1) = 3
Hence, Median array = {4 2 4 3 3}

Input: Tree = 
               25
             /    \
           20      30
         /    \   /   \
       18     22 24   32 
Output: 18 20 20 24 30 30 32

Approach:

First, find the preorder, postorder and inorder traversal of the given binary tree and store them each in a vector.
Now, for each position from 0 to N, insert the values at that position in each of the traversal arrays into a vector. The vector will be of 3N size.
Finally, sort this vector, and the median for this position is given by the 2nd element. In this vector, it has 3N elements. Therefore after sorting, the median will be given by the middle element, the 2nd element, in every 3 elements.

Below is the implementation of the above approach:

CPP

// C++ program to Obtain the median 
// array for the preorder, postorder 
// and inorder traversal of a binary tree 
   
#include <bits/stdc++.h> 
using namespace std; 
   
// A binary tree node has data, 
// a pointer to the left child 
// and a pointer to the right child 
struct Node { 
    int data; 
    struct Node *left, *right; 
    Node(int data) 
    { 
        this->data = data; 
        left = right = NULL; 
    } 
}; 
   
// Postorder traversal 
void Postorder( 
    struct Node* node, 
    vector<int>& postorder) 
{ 
    if (node == NULL) 
        return; 
   
    // First recur on left subtree 
    Postorder(node->left, postorder); 
   
    // then recur on right subtree 
    Postorder(node->right, postorder); 
   
    // now deal with the node 
    postorder.push_back(node->data); 
} 
   
// Inorder traversal 
void Inorder( 
    struct Node* node, 
    vector<int>& inorder) 
{ 
    if (node == NULL) 
        return; 
   
    // First recur on left child 
    Inorder(node->left, inorder); 
   
    // then print the data of node 
    inorder.push_back(node->data); 
   
    // now recur on right child 
    Inorder(node->right, inorder); 
} 
   
// Preorder traversal 
void Preorder( 
    struct Node* node, 
    vector<int>& preorder) 
{ 
    if (node == NULL) 
        return; 
   
    // First print data of node 
    preorder.push_back(node->data); 
   
    // then recur on left subtree 
    Preorder(node->left, preorder); 
   
    // now recur on right subtree 
    Preorder(node->right, preorder); 
} 
   
// Function to print the any array 
void PrintArray(vector<int> median) 
{ 
    for (int i = 0; 
         i < median.size(); i++) 
        cout << median[i] << " "; 
   
    return; 
} 
   
// Function to create and print 
// the Median array 
void MedianArray(struct Node* node) 
{ 
    // Vector to store 
    // the median values 
    vector<int> median; 
   
    if (node == NULL) 
        return; 
   
    vector<int> preorder, 
        postorder, 
        inorder; 
   
    // Traverse the tree 
    Postorder(node, postorder); 
    Inorder(node, inorder); 
    Preorder(node, preorder); 
   
    int n = preorder.size(); 
    for (int i = 0; i < n; i++) { 
   
        // Temporary vector to sort 
        // the three values 
        vector<int> temp; 
   
        // Insert the values at ith index 
        // for each traversal into temp 
        temp.push_back(postorder[i]); 
        temp.push_back(inorder[i]); 
        temp.push_back(preorder[i]); 
   
        // Sort the temp vector to 
        // find the median 
        sort(temp.begin(), temp.end()); 
   
        // Insert the middle value in 
        // temp into the median vector 
        median.push_back(temp[1]); 
    } 
   
    PrintArray(median); 
    return; 
} 
   
// Driver Code 
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); 
   
    MedianArray(root); 
   
    return 0; 
}

Java

// Java program to Obtain the median 
// array for the preorder, postorder 
// and inorder traversal of a binary tree 
import java.io.*;
import java.util.*; 
 
// A binary tree node has data, 
// a pointer to the left child 
// and a pointer to the right child 
class Node
{
  int data;
  Node left,right;
  Node(int item)
  {
    data = item;
    left = right = null;
  }
}
class Tree {
  public static Vector<Integer> postorder = new Vector<Integer>();
  public static Vector<Integer> inorder = new Vector<Integer>();
  public static Vector<Integer> preorder = new Vector<Integer>();
  public static Node root;
 
  // Postorder traversal 
  public static void Postorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left subtree 
    Postorder(node.left);
 
    // then recur on right subtree 
    Postorder(node.right);
 
    // now deal with the node
    postorder.add(node.data);
  }
  // Inorder traversal 
  public static void Inorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left child 
    Inorder(node.left);
 
    // then print the data of node 
    inorder.add(node.data);
 
    // now recur on right child
    Inorder(node.right);       
  }
 
  // Preorder traversal 
  public static void Preorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First print data of node 
    preorder.add(node.data);
 
    // then recur on left subtree
    Preorder(node.left);
 
    // now recur on right subtree 
    Preorder(node.right);
  }
 
  // Function to print the any array     
  public static void PrintArray(Vector<Integer> median)
  {
    for(int i = 0; i < median.size(); i++)
    {
      System.out.print(median.get(i) + " ");
    }
  }
 
  // Function to create and print 
  // the Median array
  public static void MedianArray(Node node)
  {
 
    // Vector to store 
    // the median values 
    Vector<Integer> median = new Vector<Integer>();
    if(node == null)
    {
      return;
    }
 
    // Traverse the tree
    Postorder(node); 
    Inorder(node); 
    Preorder(node); 
    int n = preorder.size();
    for(int i = 0; i < n; i++)
    {
 
      // Temporary vector to sort 
      // the three values 
      Vector<Integer> temp = new Vector<Integer>();
 
      // Insert the values at ith index 
      // for each traversal into temp 
      temp.add(postorder.get(i));
      temp.add(inorder.get(i));
      temp.add(preorder.get(i));
 
      // Sort the temp vector to 
      // find the median
      Collections.sort(temp);
 
      // Insert the middle value in 
      // temp into the median vector 
      median.add(temp.get(1));
    }
    PrintArray(median);
  }
 
  // Driver Code 
  public static void main (String[] args) 
  {
    Tree.root = new Node(1);
    Tree.root.left = new Node(2);
    Tree.root.right = new Node(3);
    Tree.root.left.left = new Node(4);
    Tree.root.left.right = new Node(5);
    MedianArray(root);
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to Obtain the median
# array for the preorder, postorder
# and inorder traversal of a binary tree
 
 
# A binary tree node has data,
# a pointer to the left child
# and a pointer to the right child
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
 
# Postorder traversal
def Postorder(node):
    global preorder
    if (node == None):
        return
    # First recur on left subtree
    Postorder(node.left)
 
    # then recur on right subtree
    Postorder(node.right)
 
    # now deal with the node
    postorder.append(node.data)
 
# Inorder traversal
def Inorder(node):
    global inorder
    if (node == None):
        return
 
    # First recur on left child
    Inorder(node.left)
 
    # then print the data of node
    inorder.append(node.data)
 
    # now recur on right child
    Inorder(node.right)
 
# Preorder traversal
def Preorder(node):
    global preorder
 
    if (node == None):
        return
 
    # First print data of node
    preorder.append(node.data)
 
    # then recur on left subtree
    Preorder(node.left)
 
    # now recur on right subtree
    Preorder(node.right)
 
# Function to print the any array
def PrintArray(median):
    for i in range(len(median)):
        print(median[i], end = " ")
 
    return
 
# Function to create and print
# the Median array
def MedianArray(node):
    global inorder, postorder, preorder
 
    # Vector to store
    # the median values
    median = []
 
    if (node == None):
        return
 
    # Traverse the tree
    Postorder(node)
    Inorder(node)
    Preorder(node)
 
    n = len(preorder)
 
    for i in range(n):
 
        # Temporary vector to sort
        # the three values
        temp = []
 
        # Insert the values at ith index
        # for each traversal into temp
        temp.append(postorder[i])
        temp.append(inorder[i])
        temp.append(preorder[i])
 
        # Sort the temp vector to
        # find the median
        temp = sorted(temp)
 
        # Insert the middle value in
        # temp into the median vector
        median.append(temp[1])
 
    PrintArray(median)
 
# Driver Code
if __name__ == '__main__':
    preorder, inorder, postorder = [], [], []
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
 
    MedianArray(root)
 
# This code is contributed by mohit kumar 29

C#

// C# program to Obtain the median 
// array for the preorder, postorder 
// and inorder traversal of a binary tree 
using System;
using System.Collections.Generic;
using System.Numerics;
 
// A binary tree node has data, 
// a pointer to the left child 
// and a pointer to the right child 
public class Node
{
  public int data;
  public Node left,right;
  public Node(int item)
  {
    data = item;
    left = right = null;
  }
}
public class Tree{
  static List<int> postorder = new List<int>();
  static List<int> inorder = new List<int>();
  static List<int> preorder = new List<int>();
 
  static Node root;
  // Postorder traversal 
  public static void Postorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left subtree 
    Postorder(node.left);
 
    // then recur on right subtree 
    Postorder(node.right);
 
    // now deal with the node
    postorder.Add(node.data);
  }
  // Inorder traversal 
  public static void Inorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First recur on left child 
    Inorder(node.left);
 
    // then print the data of node 
    inorder.Add(node.data);
 
    // now recur on right child
    Inorder(node.right);       
  }
  // Preorder traversal 
  public static void Preorder(Node node)
  {
    if(node == null)
    {
      return;
    }
 
    // First print data of node 
    preorder.Add(node.data);
 
    // then recur on left subtree
    Preorder(node.left);
 
    // now recur on right subtree 
    Preorder(node.right);
  }
 
  // Function to print the any array     
  public static void PrintArray(List<int> median)
  {
    for(int i = 0; i < median.Count; i++)
    {
      Console.Write(median[i] + " ");
    }
  }
 
  // Function to create and print 
  // the Median array
  public static void MedianArray(Node node)
  {
 
    // Vector to store 
    // the median values 
    List<int> median = new List<int>();
    if(node == null)
    {
      return;
    }
 
    // Traverse the tree
    Postorder(node); 
    Inorder(node); 
    Preorder(node); 
    int n = preorder.Count;
    for(int i = 0; i < n; i++)
    {
 
      // Temporary vector to sort 
      // the three values 
      List<int> temp = new List<int>();
 
      // Insert the values at ith index 
      // for each traversal into temp 
      temp.Add(postorder[i]);
      temp.Add(inorder[i]);
      temp.Add(preorder[i]);
 
      // Sort the temp vector to 
      // find the median
      temp.Sort();
 
      // Insert the middle value in 
      // temp into the median vector 
      median.Add(temp[1]);
    }
    PrintArray(median);
  }
 
  // Driver code
  static public void Main ()
  {
    Tree.root = new Node(1);
    Tree.root.left = new Node(2);
    Tree.root.right = new Node(3);
    Tree.root.left.left = new Node(4);
    Tree.root.left.right = new Node(5);
    MedianArray(root);
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
 
// JavaScript program to Obtain the median
// array for the preorder, postorder
// and inorder traversal of a binary tree
 
// A binary tree node has data,
// a pointer to the left child
// and a pointer to the right child
class Node
{
    constructor(item)
    {
        this.data = item;
        this.left = this.right = null;
    }
}
 
let postorder = [];
let inorder = [];
let preorder = [];
 
// Postorder traversal
function Postorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First recur on left subtree
    Postorder(node.left);
  
    // then recur on right subtree
    Postorder(node.right);
  
    // now deal with the node
    postorder.push(node.data);
}
 
// Inorder traversal
function Inorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First recur on left child
    Inorder(node.left);
  
    // then print the data of node
    inorder.push(node.data);
  
    // now recur on right child
    Inorder(node.right);   
}
 
// Preorder traversal
function Preorder(node)
{
    if(node == null)
    {
      return;
    }
  
    // First print data of node
    preorder.push(node.data);
  
    // then recur on left subtree
    Preorder(node.left);
  
    // now recur on right subtree
    Preorder(node.right);
}
// Function to print the any array 
function PrintArray(median)
{
    for(let i = 0; i < median.length; i++)
    {
      document.write(median[i] + " ");
    }
}
 
// Function to create and print
  // the Median array
function MedianArray(node)
{
    // Vector to store
    // the median values
    let median = [];
    if(node == null)
    {
      return;
    }
  
    // Traverse the tree
    Postorder(node);
    Inorder(node);
    Preorder(node);
    let n = preorder.length;
    for(let i = 0; i < n; i++)
    {
  
      // Temporary vector to sort
      // the three values
      let temp = [];
  
      // Insert the values at ith index
      // for each traversal into temp
      temp.push(postorder[i]);
      temp.push(inorder[i]);
      temp.push(preorder[i]);
  
      // Sort the temp vector to
      // find the median
      temp.sort(function(a,b){return a-b;});
  
      // Insert the middle value in
      // temp into the median vector
      median.push(temp[1]);
    }
    PrintArray(median);
}
 
 // Driver Code
let 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);
MedianArray(root);
         
// This code is contributed by patel2127
 
</script>

Output:

4 2 4 3 3

Time Complexity: O(N)
Auxiliary Space: O(N) as vectors has been created for storing preorder, inorder and postorder traversal of the tree.

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!

Find the median array for Binary tree

CPP

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

Forget Bluetooth — this Android feature makes sharing files to a Mac ridiculously easy

EDITOR PICKS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR POSTS

Google’s 15 year old Pixel concept. [Video]

The one feature Samsung Wallet still can’t get right — and probably never will

I regret trading in my Pixel 8 so early

POPULAR CATEGORY

ABOUT US

FOLLOW US