Median of all nodes from a given range in a Binary Search Tree ( BST ) | 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 ; Given BST
class Node { constructor ( key ) { this . left = null ; this . right = null ; this . key = key ; } } let interNodes = [ ] ; function newNode ( key ) { let temp = new Node ( key ) ; return temp ; } function insertNode ( node , 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 ; } function getIntermediateNodes ( root , node1 , node2 ) { if ( root == null ) return ; getIntermediateNodes ( root . left , node1 , node2 ) ; if ( root . key <= node2 && root . key >= node1 ) { interNodes . push ( root . key ) ; } getIntermediateNodes ( root . right , node1 , node2 ) ; } function findMedian ( root , node1 , node2 ) { getIntermediateNodes ( root , node1 , node2 ) ; let nSize = interNodes . length ; return ( nSize % 2 == 1 ) ? interNodes [ parseInt ( nSize / 2 , 10 ) ] : ( interNodes [ parseInt ( ( nSize - 1 ) / 2 , 10 ) ] + interNodes [ nSize / 2 ] ) / 2 ; } 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 ) ) ;