The gates of the canal

Problem

Eleuterio looks after the water of the village fields and shares out what comes down the canal. At every gate the canal splits into two branches: on the left the water goes toward the plots with a number smaller than the gate's, and on the right toward the ones with a larger number. Today one plot gets watered and someone has to write down where the water goes.

The network arrives as a dictionary, which in JavaScript is an object, with the key number and the keys left and right, which hold another dictionary just like it. A gate at the end of the canal simply doesn't carry those keys: from there on there is nowhere left to go.

You get the main gate and the number of the plot, and you return the list of numbers of the gates the water runs through, from the main one to the one that has the plot's number, that one included. If the water reaches a gate and there is no other gate on the side it needs, then that plot is not in the network and you return an empty list.

For example, with main gate 50, which has 20 on the left and 75 on the right, the water for plot 75 runs through 50 and 75, and you return 50 and 75. For plot 60 the water runs through 50 and reaches 75, but 75 has no gate on the left any more: you return an empty list.

The canal has no more than 11 gates, and the water never runs through more than 5 gates to reach its plot, counting the main one.

Idea: you don't have to walk the whole network. Stand on the gate and write it down. If its number is the plot's, you already got there. If the plot is smaller, you go through left, and if it is larger, through right. Before going down, check whether that key exists: in Python with in, and in JavaScript by comparing what the key gives you with undefined.

Examples

• The example

  {"number": 50, "left": {"number": 20}, "right": {"number": 75}}, 75 → [50, 75]

• The water runs out of gates

  {"number": 50, "left": {"number": 20}, "right": {"number": 75}}, 60 → []

• The plot of the main gate

  {"number": 50, "left": {"number": 20, "left": {"number": 8}, "right": {"number": 35, "left": {"number": 28, "right": {"number": 31}}}}, "right": {"number": 75, "left": {"number": 60}, "right": {"number": 90, "left": {"number": 82}, "right": {"number": 99}}}}, 50 → [50]

• All the way down the canal

  {"number": 50, "left": {"number": 20, "left": {"number": 8}, "right": {"number": 35, "left": {"number": 28, "right": {"number": 31}}}}, "right": {"number": 75, "left": {"number": 60}, "right": {"number": 90, "left": {"number": 82}, "right": {"number": 99}}}}, 31 → [50, 20, 35, 28, 31]

• A plot at the edge

  {"number": 50, "left": {"number": 20, "left": {"number": 8}, "right": {"number": 35, "left": {"number": 28, "right": {"number": 31}}}}, "right": {"number": 75, "left": {"number": 60}, "right": {"number": 90, "left": {"number": 82}, "right": {"number": 99}}}}, 8 → [50, 20, 8]

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def path(gates, plot):
    pass

function path(gates, plot) {
}