What is the difference between Rank and Range in context of Binary Search Tree?

Question

Two BSTs(of size m and n) are given which have all values distinct but they have one value in common which is called their intersection point, output that point in minimum time complexity ?

Answer 1

First include a variable called size in every node of the tree. This value is set to the size of the tree rooted at that node. ie size = size of left sub tree + size of right sub tree + 1. Add a private method that returns the size of a tree given its pointer, ie sizeTree(Node * root) . You will use this method in determining rank() below. On all the methods below you should update size of all involved nodes during the operations. For example , when inserting a new node, update the size values of all nodes along the insert path appropriately so that the trees size variables are up to date after the insertion.

1. Add the Delete(int x) method to the tree and its aux. This deletes the value x from the tree if it is present.

2. Add a method that returns the sum of the values in the tree. Make auxSum recursive ( int Sum() and int auxSum(node * root) )

3. Add a method called int rank(int x) that returns the number of nodes in the tree that have a value less than or equal to x. Include an aux if necessary. Do not traverse the entire tree to find the value. Use size info from the tree to determine this value efficiently. This is a little tricky so think before you program. HINT: you can look in the left sub trees root node to get info on how many nodes are over there. RankDiscussion is a case chart for rank.

4. Add a method called int range(int a,int b) that returns the number of nodes in the tree that have a value greater than a and less than or equal to b. Include an aux if necessary. Call rank to find the value to return.

5. Add a method called void ChangeKey(int key, int newvalue) that changes the node that has value key to newkey and modifies the tree appropriately so it is still a BST.