Median of all nodes from a given range in a Binary Search Tree ( BST )
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 = NoneinterNodes = [] # 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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
