BOJ. Binary Search Tree (5639)

BOJ 5639: Binary Search Tree

Build the BST from preorder

The input is the preorder traversal of a binary search tree with distinct keys. In preorder, a node appears before all of its descendants. Keep the path from the root to the most recently visited node in a stack. Its top is the current insertion point. If the next key is smaller than the top key, it is the left child of the top. Otherwise, pop ancestors while their keys are smaller than the new key. The last popped node is the new key’s parent, and the new node is its right child. The remaining stack top, if any, is an ancestor whose right subtree has not yet been left.

This stack invariant makes each node enter and leave the stack at most once, so construction takes O(N) time. It also handles either chain without recursion or a sentinel that could be popped past the stack boundary.

To produce postorder iteratively, traverse in root-right-left order by pushing the left child before the right child, then write the collected values in reverse. This yields left-right-root. Every node is visited once, so output takes O(N) time and O(N) additional space. Input is read until EOF.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        Node[] ancestors = new Node[100_000];
        Node[] traversal = new Node[100_000];
        int[] postorder = new int[100_000];
        int size = 0;

        int first = input.nextInt();
        if (first == -1) return;

        Node root = new Node(first);
        ancestors[size++] = root;

        int value;
        while ((value = input.nextInt()) != -1) {
            Node node = new Node(value);
            Node parent = null;

            while (size > 0 && ancestors[size - 1].value < value) {
                parent = ancestors[--size];
            }

            if (parent == null) {
                ancestors[size - 1].left = node;
            } else {
                parent.right = node;
            }
            ancestors[size++] = node;
        }

        int traversalSize = 0;
        int postorderSize = 0;
        traversal[traversalSize++] = root;
        while (traversalSize > 0) {
            Node node = traversal[--traversalSize];
            postorder[postorderSize++] = node.value;
            if (node.left != null) traversal[traversalSize++] = node.left;
            if (node.right != null) traversal[traversalSize++] = node.right;
        }

        StringBuilder output = new StringBuilder();
        for (int i = postorderSize - 1; i >= 0; i--) {
            output.append(postorder[i]).append('\n');
        }
        System.out.print(output);
    }

    private static final class Node {
        final int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) return -1;
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            if (c == -1) return -1;

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}