Feature #6: Longest Route

Implementing the "Longest Route" feature for our "Uber" project.

Description

A city cannot be represented by a single straight road because there are numerous intersections and crossings running throughout it. In our city, there are forks in the road, making binary-tree representation possible. The furthest checkpoints of the city are leaf nodes in this binary tree; these represent the Uber service area’s limits. We want the new drivers to have a fantastic first day to kick start their career at Uber. Therefore, we want to recommend these drivers a route that would maximize the possibility of finding customers. This route should be the longest possible route so that they are bound to find a customer eventually.

We’ll be provided with the root of a binary tree structure representing our city with each node as a checkpoint. We have to find the longest path/route so that drivers are likely to find more customers.

Did you find this helpful?
Forked roads represented as a binary tree structure

Solution

As seen in the above example, the longest path is one in which there is a maximum number of edges between two nodes or checkpoints. The edges here represent the roads. As the city structure represents a binary tree, the longest path in the tree will either pass through the root node or not. Let’s explore both of ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.