convert integer array into a binary tree

Question

I can already convert an array into a binary tree using following algorithm in java:

public class TreeNode {
    public TreeNode left, right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
    }
}

public TreeNode arrayToTree(Integer[] input){
    TreeNode root = createTreeNode(input,1);
    return root;
}

private TreeNode createTreeNode(Integer[] input, int index){
    if(index<=input.length){
        Integer value = input[index-1];
        if(value!=null){
            TreeNode t = new TreeNode(value);
            t.left = createTreeNode(input, index*2);
            t.right = createTreeNode(input, index*2+1);
            return t;
        }
    }
    return null;
}

when the input is {1,null,2,null,null,3}, I get following tree:

1        
 \   
  2    
 /   
3

however I think the input {1,null,2,3} is clear enough to define a tree like above.

Any good idea to avoid the redundant nulls defined in the input array?

Editor

do necessarily need to use recursion? – Harkins

The nulls are not reduntant. If you don't specifiy the shape of the tree and the missing nodes, no program can guess them. – Coincident

@Herokiller, any better idea even without recursion is also welcome. – Editor

@user1146450 then u may use queue to add tree nodes – Harkins

@YvesDaoust They are redundant when the parent is NULL. There are encodings which use this fact. – Copulate

Answer 1

Here is a java-monster and it solves the task with the possibility of debugging

import java.util.*;

public class TreeCreator {

    public static void main(String[] args) {
        Integer[] tree = new Integer[]{1, null, 2, 3};
        TreeCreator tr = new TreeCreator();
        TreeNode treeNode = tr.fromArray(tree);
        List<Integer> list = tr.postorderTraversal(treeNode);
        list.forEach(System.out::println); // postOrder is 3 2 1

    }

    public TreeNode fromArray(Integer[] tree) {
        if (tree.length == 0) return null;
        TreeNode root = new TreeNode(tree[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        for (int i = 1; i < tree.length; i++) {
            TreeNode node = q.peek();
            if (node.left == null) {
                node.left = new TreeNode(tree[i]);
                if (tree[i] != null) q.add(node.left);
            } else if (node.right == null) {
                node.right = new TreeNode(tree[i]);
                if (tree[i] != null) q.add(node.right);
                q.remove();
            }
        }
        return root;
    }

    private static class TreeNode {
        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(Integer x) {
            val = x;
        }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        if (root == null) return l;
        funcPostOrder(root, l);
        return l;
    }

    private void funcPostOrder(TreeNode c, List<Integer> l) {
        if (c.left != null && c.left.val != null) {
            funcPostOrder(c.left, l);
        }
        if (c.right != null) {
            funcPostOrder(c.right, l);
        }
        l.add(c.val);
    }
}

more interesing example is

Integer[] tree = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};

Bifoliolate

this is not correct, using {1, null,2, 3} gives null pointer exception in fromArray – Coniine

Answer 2

If you read the tree in preorder, you will find 1, -, 2, 3, -. Just construct the tree using the same order and not looking up the string at index*2 and index*2+1, but left to right. (You can discard the final nulls if you like).

For a more "complex" example:

       1
     /   \
   2       3
    \     / \
     4   5   6
          7   8

1, 2, -, 4, 3, 5, -, 7, 6, -, 8

Coincident

Answer 3

This should solve the problem.

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

static TreeNode arrayToTree(Integer array[]) {
    return arrayToTree(array, 0);
}

static TreeNode arrayToTree(Integer array[], int index) {
    if (index >= array.length)
        return null;
    if (array[index] == null)
        return null;
    return new TreeNode(array[index], arrayToTree(array, index * 2 + 1), arrayToTree(array, index * 2 + 2));
}

Barre

Answer 4

Here is a java-monster and it solves the task with the possibility of debugging

Use Integer to prevent NPE.

public class TreeNode {
    Integer val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(Integer val) {
        this.val = val;
    }

    TreeNode(Integer val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public List<Integer> postorderTraversal() {
        List<Integer> l = new ArrayList<>();
        if (this == null) return l;
        printPostOrder(this, l);
        return l;
    }

    private void printPostOrder(TreeNode c, List<Integer> l) {
        if (c.left != null && c.left.val != null) {
            printPostOrder(c.left, l);
        }
        if (c.right != null) {
            printPostOrder(c.right, l);
        }
        l.add(c.val);
    }

    public static TreeNode fromArray(Integer[] tree) {
        if (tree.length == 0) return null;
        TreeNode root = new TreeNode(tree[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        for (int i = 1; i < tree.length; i++) {
            TreeNode node = q.peek();
            if (node.left == null) {
                node.left = new TreeNode(tree[i]);
                if (tree[i] != null) q.add(node.left);
            } else if (node.right == null) {
                node.right = new TreeNode(tree[i]);
                if (tree[i] != null) q.add(node.right);
                q.remove();
            }
        }
        return root;
    }
}


public static void main(String[] args) {
    Integer[] integers = new Integer[]{1, null, 2, 3};
    TreeNode treeNode = TreeNode.fromArray(integers);
    List<Integer> list = treeNode.postorderTraversal();
    list.forEach(System.out::println);
}

Boer

Answer 5

My TreeNode class that seems to be working perfectly fine

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreeNode {
    public Integer val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(Integer val) {
        this.val = val;
    }

    public static TreeNode fromArray(Integer[] input) {
        Integer[] parsedInput = parseInput(input);

        return createTreeNode(parsedInput, 1);
    }

    private static Integer[] parseInput(Integer[] input) {
        Map<Integer, List<Integer>> store = new HashMap<>();
        int level = 1;

        for (int i = 0; i < input.length; ) {
            List<Integer> currValues = store.getOrDefault(level, new ArrayList<>());
            if (level > 1) {
                List<Integer> prevValues = store.get(level / 2);
                int j = 0;
                while (j < prevValues.size() && prevValues.get(j) == null) {
                    j++;
                    currValues.add(null);
                    currValues.add(null);
                }
            }
            while (currValues.size() < level && i < input.length) {
                currValues.add(input[i]);
                i++;
            }

            store.put(level, currValues);
            level *= 2;
        }

        List<Integer> res = new ArrayList<>();
        int count = 0;
        for (int i = 1; i < level; i *= 2) {
            res.addAll(store.get(i));
            count += i;
            while (res.size() < count) {
                res.add(null);
            }
        }

        return res.toArray(new Integer[0]);
    }

    private static TreeNode createTreeNode(Integer[] input, int index) {
        if (index <= input.length) {
            Integer value = input[index - 1];
            if (value != null) {
                TreeNode treeNode = new TreeNode(value);
                treeNode.left = createTreeNode(input, index * 2);
                treeNode.right = createTreeNode(input, index * 2 + 1);
                return treeNode;
            }
        }
        return null;
    }
}

Example usage

TreeNode.fromArray(new Integer[]{8,3,10,1,6,null,14,null,null,4,7,13});

Sacrum