which node owns which subtree
which traversal state has already been processed
which null boundary means empty structure
which invariant the result depends on

Tree = empty
     | Node(value, leftTree, rightTree)

public final class TreeNode<T> {
    public T value;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode(T value) {
        this.value = value;
    }
}

public final class BinaryNode<T> {
    private final T value;
    private BinaryNode<T> left;
    private BinaryNode<T> right;

    public BinaryNode(T value) {
        this.value = java.util.Objects.requireNonNull(value);
    }

    public T value() {
        return value;
    }

    public BinaryNode<T> left() {
        return left;
    }

    public BinaryNode<T> right() {
        return right;
    }

    public void setLeft(BinaryNode<T> left) {
        if (left == this) {
            throw new IllegalArgumentException("node cannot be its own left child");
        }
        this.left = left;
    }

    public void setRight(BinaryNode<T> right) {
        if (right == this) {
            throw new IllegalArgumentException("node cannot be its own right child");
        }
        this.right = right;
    }
}

int[] value;
int[] left;
int[] right;

int root = 0;
int NIL = -1;

left(i)  = 2 * i + 1
right(i) = 2 * i + 2
parent(i)= (i - 1) / 2

public final class ParentNode<T> {
    T value;
    ParentNode<T> left;
    ParentNode<T> right;
    ParentNode<T> parent;
}

height(null) = 0
height(node) = 1 + max(height(left), height(right))

public static <T> void preorder(TreeNode<T> node, java.util.List<T> out) {
    if (node == null) {
        return;
    }

    out.add(node.value);
    preorder(node.left, out);
    preorder(node.right, out);
}

When preorder(node) returns, out has appended node's subtree in root-left-right order.

public static <T> void inorder(TreeNode<T> node, java.util.List<T> out) {
    if (node == null) {
        return;
    }

    inorder(node.left, out);
    out.add(node.value);
    inorder(node.right, out);
}

When inorder(node) returns, out has appended left subtree, node, right subtree.

public static <T> void postorder(TreeNode<T> node, java.util.List<T> out) {
    if (node == null) {
        return;
    }

    postorder(node.left, out);
    postorder(node.right, out);
    out.add(node.value);
}

When processing node, both child subtrees have already been fully processed.

node reference
program counter: before-left, between-left-right, after-right
local variables
partial result

height(node)

public static <T> java.util.List<T> preorderIterative(TreeNode<T> root) {
    java.util.ArrayList<T> out = new java.util.ArrayList<>();
    if (root == null) {
        return out;
    }

    java.util.ArrayDeque<TreeNode<T>> stack = new java.util.ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode<T> node = stack.pop();
        out.add(node.value);

        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }

    return out;
}

public static <T> java.util.List<T> inorderIterative(TreeNode<T> root) {
    java.util.ArrayList<T> out = new java.util.ArrayList<>();
    java.util.ArrayDeque<TreeNode<T>> stack = new java.util.ArrayDeque<>();

    TreeNode<T> current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        out.add(current.value);
        current = current.right;
    }

    return out;
}

All nodes left of the stack path have already been processed.
The stack contains ancestors whose left side has been explored but whose node value has not yet been emitted.
current points to the next subtree that must be descended left.

record Frame<T>(TreeNode<T> node, boolean expanded) {}

public static <T> java.util.List<T> postorderIterative(TreeNode<T> root) {
    java.util.ArrayList<T> out = new java.util.ArrayList<>();
    if (root == null) {
        return out;
    }

    java.util.ArrayDeque<Frame<T>> stack = new java.util.ArrayDeque<>();
    stack.push(new Frame<>(root, false));

    while (!stack.isEmpty()) {
        Frame<T> frame = stack.pop();
        TreeNode<T> node = frame.node();

        if (frame.expanded()) {
            out.add(node.value);
            continue;
        }

        stack.push(new Frame<>(node, true));
        if (node.right != null) {
            stack.push(new Frame<>(node.right, false));
        }
        if (node.left != null) {
            stack.push(new Frame<>(node.left, false));
        }
    }

    return out;
}

An unexpanded frame means: children still need processing.
An expanded frame means: both children have already been scheduled before this frame returns to the top.

public static <T> java.util.List<java.util.List<T>> levelOrder(TreeNode<T> root) {
    java.util.ArrayList<java.util.List<T>> levels = new java.util.ArrayList<>();
    if (root == null) {
        return levels;
    }

    java.util.ArrayDeque<TreeNode<T>> queue = new java.util.ArrayDeque<>();
    queue.addLast(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        java.util.ArrayList<T> level = new java.util.ArrayList<>(levelSize);

        for (int i = 0; i < levelSize; i++) {
            TreeNode<T> node = queue.removeFirst();
            level.add(node.value);

            if (node.left != null) {
                queue.addLast(node.left);
            }
            if (node.right != null) {
                queue.addLast(node.right);
            }
        }

        levels.add(level);
    }

    return levels;
}

enter node
enter left subtree
exit left subtree
between children
enter right subtree
exit right subtree
exit node

public final class EulerTour {
    private int time;
    private final java.util.IdentityHashMap<TreeNode<Integer>, Integer> tin = new java.util.IdentityHashMap<>();
    private final java.util.IdentityHashMap<TreeNode<Integer>, Integer> tout = new java.util.IdentityHashMap<>();

    public void run(TreeNode<Integer> root) {
        dfs(root);
    }

    private void dfs(TreeNode<Integer> node) {
        if (node == null) {
            return;
        }

        tin.put(node, time++);
        dfs(node.left);
        dfs(node.right);
        tout.put(node, time);
    }

    public boolean isAncestor(TreeNode<Integer> a, TreeNode<Integer> b) {
        return tin.get(a) <= tin.get(b) && tout.get(b) <= tout.get(a);
    }
}

All nodes in node's subtree receive entry times in [tin[node], tout[node]).

public static <T> int size(TreeNode<T> node) {
    if (node == null) {
        return 0;
    }
    return 1 + size(node.left) + size(node.right);
}

size(node) returns the number of reachable nodes in node's subtree.

public static <T> int height(TreeNode<T> node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

height(node) returns the number of nodes on the longest downward path from node to a leaf.

public static <T> boolean isBalancedSlow(TreeNode<T> node) {
    if (node == null) {
        return true;
    }

    int diff = Math.abs(height(node.left) - height(node.right));
    return diff <= 1 && isBalancedSlow(node.left) && isBalancedSlow(node.right);
}

public static <T> boolean isBalanced(TreeNode<T> root) {
    return checkedHeight(root) >= 0;
}

private static <T> int checkedHeight(TreeNode<T> node) {
    if (node == null) {
        return 0;
    }

    int left = checkedHeight(node.left);
    if (left < 0) {
        return -1;
    }

    int right = checkedHeight(node.right);
    if (right < 0) {
        return -1;
    }

    if (Math.abs(left - right) > 1) {
        return -1;
    }

    return 1 + Math.max(left, right);
}

checkedHeight(node) >= 0 means subtree is balanced and the value is its height.
checkedHeight(node) == -1 means subtree is not balanced.

best path through node = leftHeight + rightHeight
best path anywhere = max(leftBest, rightBest, throughNode)

public static <T> int diameterEdges(TreeNode<T> root) {
    return diameter(root).bestDiameter;
}

private record DiameterInfo(int height, int bestDiameter) {}

private static <T> DiameterInfo diameter(TreeNode<T> node) {
    if (node == null) {
        return new DiameterInfo(0, 0);
    }

    DiameterInfo left = diameter(node.left);
    DiameterInfo right = diameter(node.right);

    int height = 1 + Math.max(left.height, right.height);
    int through = left.height + right.height;
    int best = Math.max(through, Math.max(left.bestDiameter, right.bestDiameter));

    return new DiameterInfo(height, best);
}

return enough information to parent
while also computing global best inside subtree

public static <T> java.util.List<java.util.List<T>> rootToLeafPaths(TreeNode<T> root) {
    java.util.ArrayList<java.util.List<T>> result = new java.util.ArrayList<>();
    java.util.ArrayList<T> path = new java.util.ArrayList<>();
    collectPaths(root, path, result);
    return result;
}

private static <T> void collectPaths(
        TreeNode<T> node,
        java.util.ArrayList<T> path,
        java.util.List<java.util.List<T>> result) {

    if (node == null) {
        return;
    }

    path.add(node.value);

    if (node.left == null && node.right == null) {
        result.add(java.util.List.copyOf(path));
    } else {
        collectPaths(node.left, path, result);
        collectPaths(node.right, path, result);
    }

    path.remove(path.size() - 1);
}

At function entry, path contains ancestors before node.
Before return, path is restored to exactly its entry state.

public static boolean hasPathSum(TreeNode<Integer> node, int target) {
    if (node == null) {
        return false;
    }

    int remaining = target - node.value;

    if (node.left == null && node.right == null) {
        return remaining == 0;
    }

    return hasPathSum(node.left, remaining) || hasPathSum(node.right, remaining);
}

remaining is the amount still needed from the current node down to a leaf.

public static <T> TreeNode<T> lowestCommonAncestor(
        TreeNode<T> root,
        TreeNode<T> a,
        TreeNode<T> b) {

    if (root == null || root == a || root == b) {
        return root;
    }

    TreeNode<T> left = lowestCommonAncestor(root.left, a, b);
    TreeNode<T> right = lowestCommonAncestor(root.right, a, b);

    if (left != null && right != null) {
        return root;
    }

    return left != null ? left : right;
}

lca(root, a, b) returns:
- null if neither target exists in root's subtree
- a or b if exactly one target has been found
- the lowest common ancestor if both targets have been found

private record LcaInfo<T>(TreeNode<T> node, boolean foundA, boolean foundB) {}

  1        1
 /          \
2            2

public static java.util.List<String> serialize(TreeNode<Integer> root) {
    java.util.ArrayList<String> out = new java.util.ArrayList<>();
    serializePreorder(root, out);
    return out;
}

private static void serializePreorder(TreeNode<Integer> node, java.util.List<String> out) {
    if (node == null) {
        out.add("#");
        return;
    }

    out.add(Integer.toString(node.value));
    serializePreorder(node.left, out);
    serializePreorder(node.right, out);
}

public static TreeNode<Integer> deserialize(java.util.List<String> tokens) {
    java.util.Iterator<String> iterator = tokens.iterator();
    TreeNode<Integer> root = deserializePreorder(iterator);

    if (iterator.hasNext()) {
        throw new IllegalArgumentException("extra tokens after valid tree");
    }

    return root;
}

private static TreeNode<Integer> deserializePreorder(java.util.Iterator<String> iterator) {
    if (!iterator.hasNext()) {
        throw new IllegalArgumentException("missing token");
    }

    String token = iterator.next();
    if (token.equals("#")) {
        return null;
    }

    TreeNode<Integer> node = new TreeNode<>(Integer.parseInt(token));
    node.left = deserializePreorder(iterator);
    node.right = deserializePreorder(iterator);
    return node;
}

Every non-null token consumes exactly two serialized subtrees.
Every null token consumes no children.

For each node with a left subtree:
find the rightmost node in the left subtree
temporarily link it back to current
use that link to return after processing left subtree
restore the link

public static <T> java.util.List<T> morrisInorder(TreeNode<T> root) {
    java.util.ArrayList<T> out = new java.util.ArrayList<>();
    TreeNode<T> current = root;

    while (current != null) {
        if (current.left == null) {
            out.add(current.value);
            current = current.right;
        } else {
            TreeNode<T> predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }

            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                out.add(current.value);
                current = current.right;
            }
        }
    }

    return out;
}

The algorithm is correct for empty tree.

Assume algorithm is correct for left and right subtrees.
Show it is correct for node by combining child results.

traverse tree and find answer

height(node) returns the node-height of node's subtree.

contains(node, target) returns true iff target appears in node's reachable subtree.

diameter(node) returns both subtree height and best diameter inside subtree.

n = number of nodes
h = tree height
w = maximum width of any level

empty
single node
root with left only
root with right only
perfect tree
complete but not perfect
left skew
right skew
zig-zag

deserialize(serialize(tree)) has the same shape and values as tree

preorder length == size
inorder length == size
postorder length == size
level-order flattened length == size
all traversals contain the same node values

A binary tree is recursive ownership.
A traversal is a state machine over that ownership.
An algorithm is correct when its return contract is preserved for empty tree, left subtree, right subtree, and current node.