Home Trees

Modifying trees

You should use the x = change(x) pattern when modifying trees and rearranging nodes.

In particular, you should never try and get the "parent" of a tree node. Tree nodes should contain references only to their children, never to their parent.

Looking ahead in trees

When writing a recursive tree method, you should almost never "look ahead" – the current recursive call should only ever need to look at the data field(s) of the current node. It is very rarely the case that it's necessary to look at the data field(s) of the left and right subtrees.

Designing custom tree nodes

When designing custom treenode-like objects, you should take care to keep your nodes simple, and handle only node-specific logic. Any fields that contain "data" should be marked as final.

As a rough rule of thumb, if your custom node ends up looking up information or "data" stored in other nodes, it's doing too much.