Construct a complete binary tree from its linked list representation

import java.util.ArrayDeque;

import java.util.Queue;

 

// A Binary Tree Node

class TreeNode

    int knowledge;

    TreeNode left, proper;

 

    TreeNode(int knowledge)

    

        this.knowledge = knowledge;

        this.left = this.proper = null;

    

 

// A Linked Listing Node

class ListNode

    int knowledge;

    ListNode subsequent;

 

    ListNode(int knowledge)

    

        this.knowledge = knowledge;

        this.subsequent = null;

    

 

class Most important

    // Utility operate to create a brand new node with the given knowledge and

    // pushes it onto the record’s entrance

    public static ListNode push(ListNode head, int knowledge)

    

        ListNode node = new ListNode(knowledge);

        node.subsequent = head;

        node.knowledge = knowledge;

        return node;

    

 

    // Operate to carry out preorder traversal on a given binary tree.

    public static void preorder(TreeNode root)

    

        if (root == null)

            return;

        

 

        System.out.print(root.knowledge + ” “);

        preorder(root.left);

        preorder(root.proper);

    

 

    // Operate to assemble an entire binary tree from a given linked record

    public static TreeNode convertListToBinaryTree(ListNode head)

    

        // base case

        if (head == null)

            return null;

        

 

        // create the basis utilizing the primary node of the linked record

        TreeNode root = new TreeNode(head.knowledge);

 

        // transfer the top pointer to the subsequent node

        head = head.subsequent;

 

        // create a queue to retailer tree pointers and enqueue the basis node

        Queue<TreeNode> q = new ArrayDeque<>();

        q.add(root);

 

        // loop until the top of the linked record is reached

        whereas (head != null)

        

            // dequeue entrance node

            TreeNode entrance = q.ballot();

 

            // create a left little one from the subsequent node within the linked record and enqueue it

            entrance.left = new TreeNode(head.knowledge);

            q.add(entrance.left);

 

            // transfer the top pointer to the subsequent node

            head = head.subsequent;

 

            // if the linked record didn’t attain its finish

            if (head != null)

            

                // create the appropriate little one from the subsequent node within the linked record and

                // enqueue it

                entrance.proper = new TreeNode(head.knowledge);

                q.add(entrance.proper);

 

                // transfer the top pointer to the subsequent node

                head = head.subsequent;

            

        

 

        // return root of the constructed binary tree

        return root;

    

 

    public static void essential(String[] args)

    

        ListNode head = null;

        int n = 6;

 

        // assemble a linked record

        for (int i = n; i > 0; i—)

            head = push(head, i);

        

 

        TreeNode root = convertListToBinaryTree(head);

        preorder(root);