TreeZipper.java

public class HelloWorld
{
  public static void main(String[] args)
  {
    Node one = new Node(2, new Node(1, null, null), null);
    Zipper zipper = new Zipper(null, one);
    System.out.println(zipper.left().set(5).newLeft(3).up().up().set(10).newRight(15).newLeft(12).reconstruct());
  }
}

class Cons<T> {
  T value;
  Cons<T> next;
  
  Cons(T value, Cons<T> next) {
    this.value = value;
    this.next = next;
  }
  
  @Override
  public String toString() {
    return "Cons[" + value + ", " + next + ']';
  }
}

class Node {
  final int value;
  final Node left;
  final Node right;
  
  Node(int value, Node left, Node right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
  
  @Override
  public String toString() {
    return "[" + value + ", " + left + ", " + right + ']';
  }
}

abstract class Crumb {
  int value;
  
  private Crumb() {}
  
  static class LeftCrumb extends Crumb {
    Node rightTree;
    
    LeftCrumb(int value, Node rightTree) {
      this.value = value;
      this.rightTree = rightTree;
    }
    
    Node reconstruct(Node current) {
      return new Node(value, current, rightTree);
    }
    
    public String toString() {
      return "LeftCrumb[" + value + ", " + rightTree + ']';
    }
  }
  
  static class RightCrumb extends Crumb {
    Node leftTree;
    
    RightCrumb(int value, Node leftTree) {
      this.value = value;
      this.leftTree = leftTree;
    }
    
    Node reconstruct(Node current) {
      return new Node(value, leftTree, current);
    }
    
    public String toString() {
      return "RightCrumb[" + value + ", " + leftTree + ']';
    }
  }
    
  abstract Node reconstruct(Node current);	
}

class Zipper {
  final Cons<Crumb> parentsRootLast;
  final Node current;
  
  Zipper(Cons<Crumb> parentsRootLast, Node current) {
    this.parentsRootLast = parentsRootLast;
    this.current = current;
  }
  
  Zipper up() {
    return new Zipper(parentsRootLast.next, parentsRootLast.value.reconstruct(current));
  }
  
  Zipper left() {
    return new Zipper(new Cons<Crumb>(new Crumb.LeftCrumb(current.value, current.right), parentsRootLast), current.left);
  }
  
  Zipper right() {
    return new Zipper(new Cons<Crumb>(new Crumb.RightCrumb(current.value, current.left), parentsRootLast), current.right);
  }
  
  Zipper set(int value) {
    return new Zipper(parentsRootLast, new Node(value, current.left, current.right));
  }
  
  Zipper pushLeft(int newParent) {
    return new Zipper(parentsRootLast, new Node(newParent, current, null));
  }
  
  Zipper pushRight(int newParent) {
    return new Zipper(parentsRootLast, new Node(newParent, null, current));
  }
  
  Zipper replaceWithLeft() {
    return new Zipper(parentsRootLast, current.left);
  }
  
  Zipper replaceWithRight() {
    return new Zipper(parentsRootLast, current.right);
  }
  
  Zipper newLeft(int value) {
    return new Zipper(new Cons<Crumb>(new Crumb.LeftCrumb(current.value, current.right), parentsRootLast), new Node(value, null, null));
  }
  
  Zipper newRight(int value) {
    return new Zipper(new Cons<Crumb>(new Crumb.RightCrumb(current.value, current.left), parentsRootLast), new Node(value, null, null));
  }
  
  Node reconstruct() {
    return parentsRootLast == null ? current : up().reconstruct();
  }
  
  @Override
  public String toString() {
    return "Zipper[" + parentsRootLast + ", " + current + ']';
  }
}