1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/*
# Bounded region of a graph that connects 's' to 'e' defined in terms of all
# paths between 's' and 'e'. 's' can have incoming links and 'e' can have
# outgoing edges.  The graph can have cycles in it.  Each node has at most two
# outgoing edges. Additional data-structures and methods may be defined.  
# Do not add new variables in the Node.
# Node has hashCode and equals defined.
#                   +---+         +---+
#             +---->|  g |<--------+ k  +---------+
#             |     +-+-+         +---+         |
#  |   +---+  |       |             ^           |
#--+-->| s +--+       |             |           |
#      +-+-+          v             |           v         ^
#        |          +---+           |         +---+       |
#        +--------->|   |-----------+-------->| e +-------+-->
#  
                 +---+                     +---+
*/
public class Node {
  public Node left;
  public Node right;
  public int data;
}

public class BoundedGraph {
  public Node s;
  public Node e;

  public BoundedGraph(Node s, Node e) {
    this.s = s;
    this.e = e;
  }

public void printGraph() {
  Set<Node> visited = new HashSet<Node>();
  innerPrintGraph(s, e, visited);
}

private void innerPrintGraph(Node s, Node e, Set<Node> visited) {
    if (visited.contains(s)) return;
    System.out.println(s.data);
    visited.add(s);
    if (s.left != null && s != e) 
innerPrintGraph(s.left, e, visited); 
}