Abstract Automatic deduction of the drainage network direction from Landsat imagery is a problem in remote sensing. The problem can be formulated in the abstract as a consistent labeling problem which is given a set of units (stream segments), possible labels (flow directions), and constraints on the way adjacent stream segments must be labeled. The goal is to find a mapping from their units to the labels that satisfies the constraints. Consistent labeling problems can be solved by tree search algorithms. In this paper, the stream labeling problem is formulated as a consistent labeling problem. The extraction of stream and valley segments from the Landsat images is discussed, and constraints on segments which meet at junctions are given. The tree search algorithm, employing a method called forward checking, is given and is used to determine the flow direction of all the stream segments in a way that is globally consistent with the junction constraints.