As we increase the number of leaf nodes there is a relationship that exists with the total number of nodes you need to look at. I was wondering if there was a way I could express this mathematically in a clean way. Thanks!
Well, if you assume that exactly one node changed, you should only need to check
ceil(LOG(n)/LOG(2)) nodes with
ceil() being the "round up" function. Basically, you need one check per tree height level.