How to build an incomplete binary tree from array representation

I think this example can explain what's in your mind .

array : [5,4,8,11,null,17,4,7,null,null,null,5]
Tree : 

                      5
                     /  \
                    4    8
                   /    / \
                  11   17  4
                 /        /
                7        5

All answer above are regard input array as a full tree. So left.child=2idx+1 , right.child = 2idx+2 but is actually it's wrong . beacuse those

[5,4,8,11,null,17,4,7,null,null,null,5]
[5,4,8,11,null,17,4,7,null,null,null,null,null,5,null]

are different

here is my solution

public static TreeNode createTree(Integer[] array) {
    if (array == null || array.length==0) {
        return null;
    }

    Queue<TreeNode> treeNodeQueue = new LinkedList<>();
    Queue<Integer> integerQueue = new LinkedList<>();
    for (int i = 1; i < array.length; i++) {
        integerQueue.offer(array[i]);
    }

    TreeNode treeNode = new TreeNode(array[0]);
    treeNodeQueue.offer(treeNode);

    while (!integerQueue.isEmpty()){
        Integer leftVal = integerQueue.isEmpty() ? null : integerQueue.poll();
        Integer rightVal = integerQueue.isEmpty() ? null : integerQueue.poll();
        TreeNode current = treeNodeQueue.poll();
        if (leftVal !=null) {
                TreeNode left = new TreeNode(leftVal);
                current.left = left;
                treeNodeQueue.offer(left);
        }
        if (rightVal !=null){
                TreeNode right = new TreeNode(rightVal);
                current.right = right;
                treeNodeQueue.offer(right);
        }
    }
    return treeNode;
}

Thanks Steven. I converted the Java code from Steven into Python. It worked for me!

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def creatBTree(data):
    if data == None or len(data) == 0:
        return None

    treeNodeQueue = []
    integerQueue = []

    for i in range(1,len(data)):
        print(i)
        integerQueue.append(data[i])

    treeNode = TreeNode(data[0])
    treeNodeQueue.append(treeNode)

    while integerQueue:
        if integerQueue:
            leftVal = integerQueue.pop(0)
        if integerQueue:
            rightVal = integerQueue.pop(0)

        current = treeNodeQueue.pop(0)

        if leftVal is not None:
            left = TreeNode(leftVal)
            current.left = left
            treeNodeQueue.append(left)
        if rightVal is not None:
            right = TreeNode(rightVal)
            current.right = right
            treeNodeQueue.append(right)

    return treeNode

Just use recursion to traverse the nodes using the index of the array and use Integer to allow null.

private TreeNode array2Tree(Integer[] data,TreeNode root, int index){

    if(index >= data.length){
      return root;
    }

    if(data[index] != null){
      TreeNode temp =  new TreeNode(data[index]);
      root = temp;
      root.left = array2Tree(data,root.left,2*index+1);
      root.right = array2Tree(data,root.right,2*index+2);
    }

    return root;
}

I have replaced null with -1 for simplicity arr = [1, 2, 3, -1, -1, 5,6,-1,-1,-1,-1, 7, 8, -1, -1] Now this given method insert will create a complete binary from above array then convertMinus1IntoNone function will remove all nodes with -1 and make proper tree as needed in question.

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
   
def insert(root, val):
    newnode = Node(val)
    if not root:
        root = newnode
        return root
    Q = deque([root])
    while Q:
        node = Q.popleft()
        if not node.left:
            node.left = newnode
            return
        if not node.right:
            node.right = newnode
            return
        else:
            Q.append(node.left)
            Q.append(node.right)

def convertMinus1IntoNone(root):
    if root is None:
        return
    if root.left!= None:
      convertMinus1IntoNone(root.left)
      if root.left.val == -1:
          root.left = None

    if root.right!= None:
      convertMinus1IntoNone(root.right)
      if root.right.val == -1:
          root.right = None


arr = [1, 2, 3, -1, -1, 5,6,-1,-1,-1,-1, 7, 8, -1, -1]
root = insert(None, arr[0])
for i in range(1, len(arr) , 1):
    insert(root, arr[i])
convertMinus1IntoNone(root)

In Java:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * Create a tree from array using levels i.e {-2,3,4,null,null,5,null,null,null,null,null, 6 } becomes 2 le-> 3, 2 re->4, 4 le->5, 5 le->6
     * @param arr the arr to be converted to a tree
     * @return
     */
    public static TreeNode createTreeFromArray(Integer[] arr){
        TreeNode root = new TreeNode();
        return  insertLevelOrder(arr, root, 0);
    }


    static TreeNode insertLevelOrder(Integer[] arr, TreeNode root,
                                 int i)
    {

        // Base case for recursion
        if (i < arr.length) {
            if(arr[i] == null)
                return null;
            TreeNode temp = new TreeNode(arr[i]);
            root = temp;

            // insert left child
            root.left = insertLevelOrder(arr, root.left,
                     2* i + 1);

            // insert right child
            root.right = insertLevelOrder(arr, root.right,
                     2* i + 2);
        }
        return root;
    }
}