Tree — Part3
In this story, I Want to talk about Tree Measurement. Sometimes we face to question that the subject is about finding count of node Or how many nodes between x and y are valid?
My solution points to Subtrees Count. In each node, we store the Number of nodes in the Subtree rooted at that node.
To implement Subtree Count we need to modify previous story node model and add a field as a maintaining number of nodes in Subtree and after that implement a Size() method, that returns the count at the root and finally this allows to us to implement two efficient methods which names are Rank() and Select() that in continue, We will deal with them.
First, I add a new field in Node Model;
(if you want to know about other fields please check my last stories with Tree subject)
Next, I implement Size Method, that returns count at the root;
After that, The big question is; How do we fill the Count field? Where? When?
To answer this question I should say we should change a little in Insert, Update and Delete method that we visited in the last stories, but for avoiding to make this story boring, I change Insert() method and suggest you visit the final version, check my GitHub.
As I told before, We have two efficient methods which one of them named Rank, Rank() is an answer to this question, How many Keys are smaller than K (<k)? (it is easy recursive algorithm)
To access to the completed source, please check Room Project on this link, also you can find different challenges approach of LeetCode and HackerRank in the mentioned Link.
