Consider a BST which stores nodes with five fields a data fi

Consider a BST which stores nodes with five fields: a data field, a left child field, a right child field, a left tree size, and a right tree size.

Write an algorithm that implements a static getMedian method for the BST data structure. This method should take as an argument a BSTNode, which is the root of the tree. This method should return a Double, which will either be equal to the median, or will be null if the BST tree is empty.

Solution

The basic idea is to find the number of nodes and then do inorder traversal to find the n/2th element. global index=0 findNumNodes(node): return node.leftsize + node.rightsize findMedian(node): if node == null: return null cand = findMedian(node.left) if cand != null: return cand if index == n/2: return node index = index + 1 return findMedian(node.right)