Lowest Common Ancestor in a Binary Tree

/*
 * Problem : Find the LCA.
 * Input   : The tree line, then p and q.
 * Output  : The value of the LCA.
 * Approach: One recursion
 * Time    : O(n)
 * Space   : O(h)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A tree node has a value and links to the left and right child. null means: no child.
        static class TreeNode {
            int value;
            TreeNode left;
            TreeNode right;

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

        // This method builds a tree from the level order tokens. A queue keeps the nodes that still need children.
        static TreeNode build(String[] tokens) {
            if (tokens.length == 0 || tokens[0].equals("null")) {
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
            java.util.ArrayDeque<TreeNode> queue = new java.util.ArrayDeque<>();
            queue.add(root);
            int i = 1;
            while (!queue.isEmpty() && i < tokens.length) {
                TreeNode node = queue.poll();
                if (i < tokens.length && !tokens[i].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.add(node.left);
                }
                i++;
                if (i < tokens.length && !tokens[i].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(tokens[i]));
                    queue.add(node.right);
                }
                i++;
            }
            return root;
        }

        // Step 2: If this node is p or q, it is the answer for its own subtree. Otherwise ask both children.
        static TreeNode ancestor(TreeNode node, int p, int q) {
            if (node == null || node.value == p || node.value == q) {
                return node;
            }
            TreeNode left = ancestor(node.left, p, q);
            TreeNode right = ancestor(node.right, p, q);
            // Step 3: p on one side and q on the other side: this node is the lowest common ancestor.
            if (left != null && right != null) {
                return node;
            }
            return left != null ? left : right;
        }

    // This method solves the task. It receives the input and returns the answer.
    static int solve(String[] lines) {
        // Step 4: The tree is on the first line, and p and q are on the second line.
        TreeNode root = build(lines[0].split(" "));
        String[] pair = lines[1].split(" ");
        return ancestor(root, Integer.parseInt(pair[0]), Integer.parseInt(pair[1])).value;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}