BFOIT - Introduction to Computer Programming

Pitcher Problem Solver - Pouring Data Tree

The Pouring Data Structure Tree, Solution Path Through Nodes

Given pitchers of sizes 3 liters and 7 liters, walk through the pouring data structures in a tree to find the solution of 1 liter. Here is the solution provided by the solver program.

Now let's walk through the tree, one level down for each pouring step.

  1. Coming off the root node with both pitchers empty, fill pitcher two from the river. The pouring data for this level-1 node is [[0 2] 0 7].
  2. Coming off the level-1 node with pitcher one empty and pitcher two containing 7 liters, fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 3 4].
  3. Coming off the level-2 node with pitcher one containing 3 liters and pitcher two containing 4 liters, empty pitcher one into the river. The pouring data for this node is [[1 0] 0 4].
  4. Coming off the level-3 node with pitcher one empty and pitcher two containing 4 liters, fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 3 1].

Here is the tree with this path and concerned nodes highlighted.