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.

--

--

--

I have a dream to have a spectacular garden

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Seamless Data Driven API Testing as compare to SoapUI/Postman …

Web Scraping with PHP

Building API-first eCommerce dashboards with Vue.js and Deploy Now

What is Agile Methodology in Mobile App Development

Updates to Ghostwriter: UI and Operation Logs

【Hexo Website Building】The Original Intention / Cost / Tool / Theme

I Failed My First Mock Tech Interview

Reverse engineering

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ahmad Berahman

Ahmad Berahman

I have a dream to have a spectacular garden

More from Medium

Minimum Spanning Tree & Prim’s Algorithm

Leetcode Biweekly Contest 69 & Leetcode Weekly Contest 275 Overview

Validate Binary Search Tree🚂

The Essence of Algorithm: Prefix Sum