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:

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?

The nulls are not reduntant. If you don't specifiy the shape of the tree and the missing nodes, no program can guess them. — user1196549
– user1196549, Commented Nov 12, 2014 at 16:50
@Herokiller, any better idea even without recursion is also welcome. — rekinyz
– rekinyz, Commented Nov 12, 2014 at 16:52
@YvesDaoust They are redundant when the parent is NULL. There are encodings which use this fact. — ryanpattison
– ryanpattison, Commented Nov 12, 2014 at 16:56

irisha_murrr · Accepted Answer · 2019-05-29 12:23:43Z

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

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

score 2 · Accepted Answer · 2014-11-12 17:20:27Z

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

edited Nov 12, 2014 at 17:20

answered Nov 12, 2014 at 17:13

user1196549

Comments

eldho2000 · Accepted Answer · 2021-07-03 12:44:41Z

1

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

answered Jul 3, 2021 at 12:44

eldho2000

111 bronze badge

Comments

LionLoin · Accepted Answer · 2022-10-26 04:07:28Z

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

Tarun Kolla · Accepted Answer · 2024-02-26 05:37:16Z

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

Collectives™ on Stack Overflow

convert integer array into a binary tree

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related