Feature #6: Longest Route

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.

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 ...