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

in place, returning the same tree as passed, but if the original tree was empty, then a new node is
returned as result instead):
public static Tree update(String k, int newval, Tree t) {
if (t == null)
t = new Tree(k, newval, null, null);
else if (k.equals(t.key))
t.val = newval;
else if (k.compareTo(t.key) < 0)
t.left = update(k, newval, t.left);
else
t.right = update(k, newval, t.right);
return t;
}
Note that both versions of update once again mutate the existing Tree, meaning that all users of
the map stored in the tree will see the mutation.
14.2.3. Using a functional approach
So how might you do this functionally? You need to create a new node for the new key-value pair,
but you also need to create new nodes on the path from the root of the tree to the new node (in
general this isn't very expensive, if the tree is of depth d and reasonably well balanced, then it
can have 2 d entries, so you re-create only a small fraction of it):
public static Tree fupdate(String k, int newval, Tree t) {
return (t == null) ?
new Tree(k, newval, null, null) :
k.equals(t.key) ?
new Tree(k, newval, t.left, t.right) :
k.compareTo(t.key) < 0 ?
new Tree(t.key, t.val, fupdate(k,newval, t.left), t.right) :
new Tree(t.key, t.val, t.left, fupdate(k,newval, t.right));
}
We've written this as a single conditional expression instead of using if-then-else to emphasize
the idea that the body is only a single expression with no side effects, but you may prefer to write
an equivalent if-then-else chain, each containing a return.