Python Binary Search Tree Solution
Binary Search Tree implementation in python\nInspired from https://leetcode.com/problems/find-median-from-data-stream/discuss/74166/Solution-using-Binary-Search
Binary Search Tree implementation in python\nInspired from https://leetcode.com/problems/find-median-from-data-stream/discuss/74166/Solution-using-Binary-Search-Tree \n\n```\nclass Node:\n    def __init__(self, val, size=1):\n        self.val = val\n        # size represents nodes below this\n        self.size = size\n        self.left = None\n        self.right = None\n\nclass Tree:\n\n    def __init__(self):\n        self.root = None\n\n    def add_node(self, val, root=None):\n        # attach node after this node\n        if not root:\n            node = Node(val)\n            # set tree root\n            if not self.root:\n                self.root = node\n            return node\n        if val <= root.val:\n            root.left = self.add_node(val, root.left)\n        else:\n            root.right = self.add_node(val, root.right)\n        size = 1\n        if root.left:\n            size += root.left.size\n        if root.right:\n            size += root.right.size\n        root.size = size\n        return root\n\n    def rank(self, k):\n        """\n        Get k rank node\n        """\n        temp = self.root\n        while True:\n            if not temp.left:\n                left_size = 0 # handle when there is no left child\n            else:\n                left_size = temp.left.size\n            if left_size == k:\n                # Exactly k nodes in left subtree\n                # Exactly k nodes smaller than this\n                return temp.val\n            if left_size > k:\n                # Go left\n                temp = temp.left\n            else:\n                # Go right\n                # remaining number of elements which we have to look\n                # = exclude left & root (left.size + 1)\n                k = k - left_size - 1\n                temp = temp.right\n        return -1\n\n\nclass MedianFinder:\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.bst = Tree()\n        \n    def addNum(self, num):\n        """\n        Adds a num into the data structure.\n        :type num: int\n        :rtype: void\n        """\n        self.bst.add_node(num, self.bst.root)\n\n\n    def findMedian(self):\n        """\n        Returns the median of current data stream\n        :rtype: float\n        """\n        size = self.bst.root.size\n        mid = size / 2\n        if size % 2 == 0:\n            return (self.bst.rank(mid-1) + self.bst.rank(mid))/ 2.0\n        else:\n            return float(self.bst.rank(mid))\n\n```
['Binary Search Tree', 'Python']