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 : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT interNodes = [ ] NEW_LINE def newNode ( key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE return temp NEW_LINE DEDENT def insertNode ( node , key ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return newNode ( key ) NEW_LINE DEDENT if ( key < node . key ) : NEW_LINE INDENT node . left = insertNode ( node . left , key ) NEW_LINE DEDENT elif ( key > node . key ) : NEW_LINE INDENT node . right = insertNode ( node . right , key ) NEW_LINE DEDENT return node NEW_LINE DEDENT def getIntermediateNodes ( root , node1 , node2 ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT getIntermediateNodes ( root . left , node1 , node2 ) NEW_LINE if ( root . key <= node2 and root . key >= node1 ) : NEW_LINE INDENT interNodes . append ( root . key ) NEW_LINE DEDENT getIntermediateNodes ( root . right , node1 , node2 ) NEW_LINE DEDENT def findMedian ( root , node1 , node2 ) : NEW_LINE INDENT getIntermediateNodes ( root , node1 , node2 ) NEW_LINE nSize = len ( interNodes ) NEW_LINE if nSize % 2 == 1 : NEW_LINE INDENT return interNodes [ int ( nSize / 2 ) ] NEW_LINE DEDENT else : NEW_LINE INDENT return ( interNodes [ int ( ( nSize - 1 ) / 2 ) ] + interNodes [ nSize / 2 ] ) / 2 NEW_LINE DEDENT DEDENT root = None NEW_LINE root = insertNode ( root , 8 ) NEW_LINE insertNode ( root , 3 ) NEW_LINE insertNode ( root , 1 ) NEW_LINE insertNode ( root , 6 ) NEW_LINE insertNode ( root , 4 ) NEW_LINE insertNode ( root , 11 ) NEW_LINE insertNode ( root , 15 ) NEW_LINE print ( findMedian ( root , 3 , 11 ) ) NEW_LINE