Median of all nodes from a given range in a Binary Search Tree ( BST )

0 0 8 minutes read

Given a Binary Search Tree (BST)consisting of N nodes and two nodes A and B, the task is to find the median of all the nodes in the given BST whose values lie over the range [A, B].

Examples:

Input: A = 3, B = 11

Output: 6
Explanation:
The nodes that lie over the range [3, 11] are {3, 4, 6, 8, 11}. The median of the given nodes is 6.

Input: A = 6, B = 15

Output: 9.5

Approach: The given problem can be solved by performing any tree traversal on the given tree and store all the nodes lies over the range [A, B], and find the median of all the stored element. Follow the steps below to solve the problem:

Initialize a vector, say V that stores all the values of the tree that lies over the range [A, B].
Perform the Inorder traversal of the given tree and if any node’s value lies over the range [A, B] then insert that value in the vector V.
After completing the above steps, print the value of the median of all the elements stored in vector V as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Tree Node structure
struct Node {
    struct Node *left, *right;
    int key;
};
 
// Function to create a new BST node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Function to insert a new node with
// given key in BST
Node* insertNode(Node* node, int key)
{
    // If the tree is empty,
    // return a new node
    if (node == NULL)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insertNode(
            node->left, key);
 
    else if (key > node->key)
        node->right = insertNode(
            node->right, key);
 
    // Return the node pointer
    return node;
}
 
// Function to find all the nodes that
// lies over the range [node1, node2]
void getIntermediateNodes(
    Node* root, vector<int>& interNodes,
    int node1, int node2)
{
    // If the tree is empty, return
    if (root == NULL)
        return;
 
    // Traverse for the left subtree
    getIntermediateNodes(root->left,
                         interNodes,
                         node1, node2);
 
    // If a second node is found,
    // then update the flag as false
    if (root->key <= node2
        and root->key >= node1) {
        interNodes.push_back(root->key);
    }
 
    // Traverse the right subtree
    getIntermediateNodes(root->right,
                         interNodes,
                         node1, node2);
}
 
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
float findMedian(Node* root, int node1,
                 int node2)
{
    // Stores all the nodes in
    // the range [node1, node2]
    vector<int> interNodes;
 
    getIntermediateNodes(root, interNodes,
                         node1, node2);
 
    // Store the size of the array
    int nSize = interNodes.size();
 
    // Print the median of array
    // based on the size of array
    return (nSize % 2 == 1)
               ? (float)interNodes[nSize / 2]
               : (float)(interNodes[(nSize - 1) / 2]
                         + interNodes[nSize / 2])
                     / 2;
}
 
// Driver Code
int main()
{
    // Given BST
    struct Node* root = NULL;
    root = insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 4);
    insertNode(root, 11);
    insertNode(root, 15);
 
    cout << findMedian(root, 3, 11);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Tree Node structure
static class Node 
{
    Node left, right;
    int key;
};
 
static Vector<Integer> interNodes = new Vector<Integer>();
 
// Function to create a new BST node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
// Function to insert a new node with
// given key in BST
static Node insertNode(Node node, int key)
{
     
    // If the tree is empty,
    // return a new node
    if (node == null)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node.key)
        node.left = insertNode(
            node.left, key);
 
    else if (key > node.key)
        node.right = insertNode(
            node.right, key);
 
    // Return the node pointer
    return node;
}
 
// Function to find all the nodes that
// lies over the range [node1, node2]
static void getIntermediateNodes(Node root, 
                                 int node1, 
                                 int node2)
{
     
    // If the tree is empty, return
    if (root == null)
        return;
 
    // Traverse for the left subtree
    getIntermediateNodes(root.left,
                         node1, node2);
 
    // If a second node is found,
    // then update the flag as false
    if (root.key <= node2 && 
        root.key >= node1)
    {
        interNodes.add(root.key);
    }
 
    // Traverse the right subtree
    getIntermediateNodes(root.right,
                         node1, node2);
}
 
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
static float findMedian(Node root, int node1,
                                   int node2)
{
     
    // Stores all the nodes in
    // the range [node1, node2]
    getIntermediateNodes(root,
                         node1, node2);
 
    // Store the size of the array
    int nSize = interNodes.size();
 
    // Print the median of array
    // based on the size of array
    return (nSize % 2 == 1) ? 
           (float)interNodes.get(nSize / 2) : 
           (float)(interNodes.get((nSize - 1) / 2) + 
                    interNodes.get(nSize / 2)) / 2;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given BST
    Node root = null;
    root = insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 4);
    insertNode(root, 11);
    insertNode(root, 15);
 
    System.out.print(findMedian(root, 3, 11));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach
 
# Tree Node structure
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
interNodes = []
   
# Function to create a new BST node
def newNode(key):
    temp = Node(key)
    return temp
 
# Function to insert a new node with
# given key in BST
def insertNode(node, key):
    # If the tree is empty,
    # return a new node
    if (node == None):
        return newNode(key)
 
    # Otherwise, recur down the tree
    if (key < node.key):
        node.left = insertNode(node.left, key)
    elif (key > node.key):
        node.right = insertNode(node.right, key)
 
    # Return the node pointer
    return node
 
# Function to find all the nodes that
# lies over the range [node1, node2]
def getIntermediateNodes(root, node1, node2):
    # If the tree is empty, return
    if (root == None):
        return
 
    # Traverse for the left subtree
    getIntermediateNodes(root.left, node1, node2)
 
    # If a second node is found,
    # then update the flag as false
    if (root.key <= node2 and root.key >= node1):
        interNodes.append(root.key)
 
    # Traverse the right subtree
    getIntermediateNodes(root.right, node1, node2)
 
# Function to find the median of all
# the values in the given BST that
# lies over the range [node1, node2]
def findMedian(root, node1, node2):
    # Stores all the nodes in
    # the range [node1, node2]
    getIntermediateNodes(root, node1, node2)
 
    # Store the size of the array
    nSize = len(interNodes)
 
    # Print the median of array
    # based on the size of array
    if nSize % 2 == 1:
        return interNodes[int(nSize / 2)]
    else:
        return (interNodes[int((nSize - 1) / 2)] + interNodes[nSize / 2]) / 2
 
# Given BST
root = None
root = insertNode(root, 8)
insertNode(root, 3)
insertNode(root, 1)
insertNode(root, 6)
insertNode(root, 4)
insertNode(root, 11)
insertNode(root, 15)
 
print(findMedian(root, 3, 11))
 
# This code is contributed by decode2207.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Tree Node structure
class Node 
{
    public Node left, right;
    public int key;
};
 
static List<int> interNodes = new List<int>();
 
// Function to create a new BST node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
// Function to insert a new node with
// given key in BST
static Node insertNode(Node node, int key)
{
     
    // If the tree is empty,
    // return a new node
    if (node == null)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node.key)
        node.left = insertNode(
            node.left, key);
 
    else if (key > node.key)
        node.right = insertNode(
            node.right, key);
 
    // Return the node pointer
    return node;
}
 
// Function to find all the nodes that
// lies over the range [node1, node2]
static void getIntermediateNodes(Node root, 
                                 int node1, 
                                 int node2)
{
     
    // If the tree is empty, return
    if (root == null)
        return;
 
    // Traverse for the left subtree
    getIntermediateNodes(root.left,
                         node1, node2);
 
    // If a second node is found,
    // then update the flag as false
    if (root.key <= node2 && 
        root.key >= node1)
    {
        interNodes.Add(root.key);
    }
 
    // Traverse the right subtree
    getIntermediateNodes(root.right,
                         node1, node2);
}
 
// Function to find the median of all
// the values in the given BST that
// lies over the range [node1, node2]
static float findMedian(Node root, int node1,
                                   int node2)
{
     
    // Stores all the nodes in
    // the range [node1, node2]
    getIntermediateNodes(root,
                         node1, node2);
 
    // Store the size of the array
    int nSize = interNodes.Count;
 
    // Print the median of array
    // based on the size of array
    return (nSize % 2 == 1) ? 
           (float)interNodes[nSize / 2] : 
           (float)(interNodes[(nSize - 1) / 2] + 
                    interNodes[nSize / 2]) / 2;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given BST
    Node root = null;
    root = insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 4);
    insertNode(root, 11);
    insertNode(root, 15);
 
    Console.Write(findMedian(root, 3, 11));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
    // Javascript program for the above approach
     
    // Tree Node structure
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
     
    let interNodes = [];
  
    // Function to create a new BST node
    function newNode(key)
    {
        let temp = new Node(key);
        return temp;
    }
 
    // Function to insert a new node with
    // given key in BST
    function insertNode(node, key)
    {
 
        // If the tree is empty,
        // return a new node
        if (node == null)
            return newNode(key);
 
        // Otherwise, recur down the tree
        if (key < node.key)
            node.left = insertNode(
                node.left, key);
 
        else if (key > node.key)
            node.right = insertNode(
                node.right, key);
 
        // Return the node pointer
        return node;
    }
 
    // Function to find all the nodes that
    // lies over the range [node1, node2]
    function getIntermediateNodes(root, node1, node2)
    {
 
        // If the tree is empty, return
        if (root == null)
            return;
 
        // Traverse for the left subtree
        getIntermediateNodes(root.left,
                             node1, node2);
 
        // If a second node is found,
        // then update the flag as false
        if (root.key <= node2 &&
            root.key >= node1)
        {
            interNodes.push(root.key);
        }
 
        // Traverse the right subtree
        getIntermediateNodes(root.right,
                             node1, node2);
    }
 
    // Function to find the median of all
    // the values in the given BST that
    // lies over the range [node1, node2]
    function findMedian(root, node1, node2)
    {
 
        // Stores all the nodes in
        // the range [node1, node2]
        getIntermediateNodes(root, node1, node2);
 
        // Store the size of the array
        let nSize = interNodes.length;
 
        // Print the median of array
        // based on the size of array
        return (nSize % 2 == 1) ?
               interNodes[parseInt(nSize / 2, 10)] :
               (interNodes[parseInt((nSize - 1) / 2, 10)] +
                        interNodes[nSize / 2]) / 2;
    }
     
    // Given BST
    let root = null;
    root = insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 4);
    insertNode(root, 11);
    insertNode(root, 15);
  
    document.write(findMedian(root, 3, 11));
 
// This code is contributed by suresh07.
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

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 zambiatek!