educative.io

Time complexity of matching a user location to a leaf node

Hi @Design_Gurus (or anybody else please feel free to chime in)

What is the time complexity of this operation:

How will we find the grid for a given location? We will start with the root node and search downward to find our required node/grid. At each step, we will see if the current node we are visiting has children. If it has, we will move to the child node that contains our desired location and repeat this process. If the node does not have any children, then that is our desired node.”

Hi @milo_t

Time complexity would be O(h) where h will be the height of the tree, as you have to traverse till the leaf node.

1 Like