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 structurestruct Node {Â Â Â Â struct Node *left, *right;Â Â Â Â int key;};Â
// Function to create a new BST nodeNode* 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 BSTNode* 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 Codeint 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 approachimport java.util.*;Â
class GFG{Â
// Tree Node structurestatic class Node {Â Â Â Â Node left, right;Â Â Â Â int key;};Â
static Vector<Integer> interNodes = new Vector<Integer>();Â
// Function to create a new BST nodestatic 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 BSTstatic 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 Codepublic 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 structureclass Node:    def __init__(self, key):        self.key = key        self.left = None        self.right = NoneÂ
interNodes = []Â Â Â # Function to create a new BST nodedef newNode(key):Â Â Â Â temp = Node(key)Â Â Â Â return tempÂ
# Function to insert a new node with# given key in BSTdef 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 BSTroot = Noneroot = 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 approachusing System;using System.Collections.Generic;Â
public class GFG{Â
// Tree Node structureclass Node {Â Â Â Â public Node left, right;Â Â Â Â public int key;};Â
static List<int> interNodes = new List<int>();Â
// Function to create a new BST nodestatic 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 BSTstatic 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 Codepublic 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:Â
6
Â
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/median-of-all-nodes-from-a-given-range-in-a-binary-search-tree-bst/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/median-of-all-nodes-from-a-given-range-in-a-binary-search-tree-bst/ […]