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