Trees and BSTs

Tree definition

A binary-tree node stores a value plus references to at most two child nodes. Java classes may contain fields of their own type; this self-referential pattern also appears in linked lists and graphs.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

For example:

    1
   / \
  2   3

TreeNode leftChild = new TreeNode(2);
TreeNode rightChild = new TreeNode(3);
TreeNode root = new TreeNode(1, leftChild, rightChild);

Tree traversals

For this tree:

        1
       / \
      2   3
     / \   \
    4   5   6

• Level order: 1, 2, 3, 4, 5, 6
• Preorder: 1, 2, 4, 5, 3, 6
• Inorder: 4, 2, 5, 1, 3, 6
• Postorder: 4, 5, 2, 6, 3, 1

Preorder

Visit root, left, right. Because the node is handled before its children, preorder works well for constructing, copying, or printing a tree.

void preorder(TreeNode node) {
    if (node == null) return;
    visit(node);
    preorder(node.left);
    preorder(node.right);
}

Inorder

Visit left, root, right. An inorder traversal of a binary search tree produces values in sorted order.

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    visit(node);
    inorder(node.right);
}

Postorder

Visit left, right, root. Children are processed before their parent, which is useful when a parent depends on results returned by its subtrees, when deleting a tree, and during backtracking.

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    visit(node);
}

Level order

Use a queue to visit nodes from top to bottom and left to right. This is the tree form of BFS and is useful for shortest root-to-node paths and level-based processing.

List<Integer> levelOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return result;
}

Recursive design notes

Decide whether a recursive tree function needs a return value:

• Use no return value when every node must be visited and the parent does not consume a child result, such as collecting all root-to-leaf paths.
• Return a value when the parent must combine information from its subtrees, such as height, balance, or a lowest common ancestor.
• Return a value immediately when the search needs only one qualifying path.

A dependable recursive workflow is:

1. Define parameters and the return value.
2. Define the base case.
3. Define the work performed at one node.

Tree construction usually uses preorder logic: construct the current root, then recursively construct its left and right subtrees. When splitting an input array, prefer index ranges over allocating new subarrays.

Whether to guard before a recursive call is primarily a style choice. If null nodes enter the function, the base case handles them; otherwise, guard at the call site.

Binary search trees

A binary search tree is ordered:

• Every value in the left subtree is smaller than the root value.
• Every value in the right subtree is larger than the root value.
• Both subtrees are themselves binary search trees.

The ordering provides direction. To search for target, move left when target < root.val and right when target > root.val. Unlike a general binary tree, there is no need to backtrack into the discarded direction.

An inorder traversal yields the values in sorted order. A postorder traversal naturally moves information from the bottom upward, which makes it a strong choice for ancestor and subtree-result problems. Insertions and deletions are often cleanest when the recursive function returns the new root of the modified subtree.