MaximumBinaryTreeSolution

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

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;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length - 1);
    }

    public TreeNode construct(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }

        int maxIdx = findMaxIndex(nums, low, high);
        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left = construct(nums, low, maxIdx - 1);
        root.right = construct(nums, maxIdx + 1, high);
        return root;
    }

    public int findMaxIndex(int[] nums, int low, int high) {
        int maxIdx = low;
        for (int i = low + 1; i <= high; i++) {
            if (nums[i] > nums[maxIdx]) {
                maxIdx = i;
            }
        }
        return maxIdx;
    }

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current != null) {
                result.add(current.val);
                queue.offer(current.left);
                queue.offer(current.right);
            } else {
                boolean allNull = true;
                for (TreeNode node : queue) {
                    if (node != null) {
                        allNull = false;
                        break;
                    }
                }
                if (!allNull) {
                    result.add(null);
                }
            }
        }

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TreeNode node = new TreeNode();
        System.out.print("Enter the size: ");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        TreeNode root = node.constructMaximumBinaryTree(nums);
        List<Integer> tree = node.LevelwiseOrderTraversal(root);
        System.out.println("Maximum Binary Tree:");
        System.out.println(tree);
    }
}

// results:

// Input: nums = [3,2,1,6,0,5]
// Output: [6,3,5,null,2,0,null,null,1]

// nums = [3,2,1]
// Output: [3,null,2,null,1]