Serializing Binary Search Trees

To serialize a binary search tree (BST), we can utilize the properties of pre-order traversal. By recording node values as they are visited, we capture the structure necessary to reconstruct the tree. During deserialization, the bounds constraint imposed by the BST property (left subtree values must be smaller than the root, right subtree values must be larger) allows us to reconstruct the original tree uniquely from the serialized data.

The following implemantation uses a StringBuilder for compact string formatting during serialization. The deserialization process leverages recursion with range checks (min, max) to ensure valid BST reconstruction without relying on structural markers like null pointers in the string format.

import java.util.*;

class Codec {
    // Stores the current state of string building during traversal
    private StringBuilder buffer;

    public Codec() {
        this.buffer = new StringBuilder();
    }

    /**
     * Encodes a tree to a single comma-separated string.
     * Uses Pre-order traversal: Root -> Left -> Right
     */
    public String serialize(TreeNode root) {
        buildString(root);
        // Remove trailing comma if exists
        if (buffer.length() > 0) {
            buffer.setLength(buffer.length() - 1);
        }
        return buffer.toString();
    }

    /**
     * Decodes the encoded string back into the original tree structure.
     * Pumps the split values into a list for sequential processing.
     */
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] parts = data.split(", ");
        Queue<Integer> queue = new LinkedList<>();
        for (String p : parts) {
            if (!p.trim().isEmpty()) {
                queue.offer(Integer.parseInt(p.trim()));
            }
        }
        return constructTree(queue, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    /**
     * Helper method to append value to buffer recursively.
     */
    private void buildString(TreeNode node) {
        if (node == null) {
            return;
        }
        buffer.append(node.val).append(", ");
        buildString(node.left);
        buildString(node.right);
    }

    /**
     * Recursive construction enforcing BST constraints.
     * Checks if the current head of the queue fits within [min, max].
     */
    private TreeNode constructTree(Queue<Integer> queue, int minVal, int maxVal) {
        if (queue.isEmpty()) {
            return null;
        }
        
        int val = queue.peek();
        if (val < minVal || val > maxVal) {
            return null;
        }

        // Consume the valid node
        queue.poll();
        TreeNode currentNode = new TreeNode(val);
        
        // Build left child using the same value but tighter upper bound
        currentNode.left = constructTree(queue, minVal, currentNode.val);
        // Build right child using lower bound set to current node value
        currentNode.right = constructTree(queue, currentNode.val, maxVal);
        
        return currentNode;
    }
}

Implementing a BST Iterator

Iterating through a Binary Search Tree in ascending order typically requires an in-order traversal. A naive approach involves storing all elements in a list beforehand, which consumes $O(N)$ space. To optimize memory usage, we can simulate the in-order traversal using a stack. This approach only maintains the path from the root to the current node, resulting in $O(H)$ space complexity where $H$ is the height of the tree.

This iterator implements the standard interface methods to retrieve the next smallest integer and check if more elements remain.

import java.util.Stack;

class BSTIterator {
    private Stack<TreeNode> traversalStack;

    public BSTIterator(TreeNode root) {
        traversalStack = new Stack<>();
        pushAllLeftNodes(root);
    }

    /**
     * Returns the next smallest number.
     */
    public int next() {
        TreeNode node = traversalStack.pop();
        int result = node.val;
        pushAllLeftNodes(node.right);
        return result;
    }

    /**
     * Check if there is a next element available.
     */
    public boolean hasNext() {
        return !traversalStack.isEmpty();
    }

    /**
     * Internal helper to push all left children onto the stack.
     */
    private void pushAllLeftNodes(TreeNode node) {
        while (node != null) {
            traversalStack.push(node);
            node = node.left;
        }
    }
}

/* Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */