Functional programming techniques - Java 8 in Action: Lambdas, Streams, and Functional-Style Programming - page 379

14.2.2. Another example with Trees
Before leaving this topic, let's consider another data structure—that of a binary search tree that
might be used to implement a similar interface to a HashMap. The idea is that a Tree contains a
String representing a key and an int representing its value, perhaps names and ages:
class Tree {
private String key;
private int val;
private Tree left, right;
public Tree(String k, int v, Tree l, Tree r) {
key = k; val = v; left = l; right = r;
}
}
class TreeProcessor {
public static int lookup(String k, int defaultval, Tree t) {
if (t == null) return defaultval;
if (k.equals(t.key)) return t.val;
return lookup(k, defaultval,
k.compareTo(t.key) < 0 ? t.left : t.right);
}
// other methods processing a Tree
}
You want to make use of the binary search tree for looking up String values to produce an int.
Now consider how you might update the value associated with a given key (for simplicity you'll
start by assuming the key is already present in the tree):
public static void update(String k, int newval, Tree t) {
if (t == null) { /* should add a new node */ }
else if (k.equals(t.key)) t.val = newval;
else update(k, newval, k.compareTo(t.key) < 0 ? t.left : t.right);
}
Adding a new node is trickier; the easiest way is to make the method update return the Tree that
has just been traversed (this will be unchanged unless you had to add a new node). This code is
now slightly clumsier (because the user needs to remember that update tries to update the tree