import java.util.ArrayDeque;
import java.util.Queue;
// A Binary Tree Node
class TreeNode
{
int data;
TreeNode left, right;
TreeNode(int data)
{
this.data = data;
this.left = this.right = null;
}
}
// A Linked List Node
class ListNode
{
int data;
ListNode next;
ListNode(int data)
{
this.data = data;
this.next = null;
}
}
class Main
{
// Utility function to create a new node with the given data and
// pushes it onto the list’s front
public static ListNode push(ListNode head, int data)
{
ListNode node = new ListNode(data);
node.next = head;
node.data = data;
return node;
}
// Function to perform preorder traversal on a given binary tree.
public static void preorder(TreeNode root)
{
if (root == null) {
return;
}
System.out.print(root.data + ” “);
preorder(root.left);
preorder(root.right);
}
// Function to construct a complete binary tree from a given linked list
public static TreeNode convertListToBinaryTree(ListNode head)
{
// base case
if (head == null) {
return null;
}
// create the root using the first node of the linked list
TreeNode root = new TreeNode(head.data);
// move the head pointer to the next node
head = head.next;
// create a queue to store tree pointers and enqueue the root node
Queue
q.add(root);
// loop till the end of the linked list is reached
while (head != null)
{
// dequeue front node
TreeNode front = q.poll();
// create a left child from the next node in the linked list and enqueue it
front.left = new TreeNode(head.data);
q.add(front.left);
// move the head pointer to the next node
head = head.next;
// if the linked list did not reach its end
if (head != null)
{
// create the right child from the next node in the linked list and
// enqueue it
front.right = new TreeNode(head.data);
q.add(front.right);
// move the head pointer to the next node
head = head.next;
}
}
// return root of the constructed binary tree
return root;
}
public static void main(String[] args)
{
ListNode head = null;
int n = 6;
// construct a linked list
for (int i = n; i > 0; i—) {
head = push(head, i);
}
TreeNode root = convertListToBinaryTree(head);
preorder(root);
}
}