Construct a binary tree from a sequence of values

Question

How to construct a binary tree from a sequence of values.

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1

Input with null: [1,2,3,null,5,6,7]

       1
     /   \
    2     3
  /  \   /  \
null  5  6   7

Note: the tree is not a binary search tree. The nodes are inserted in pre order ( root, left, right ). Start by filling the child nodes from left to right. Once the level is filled, go to the next level. My intuition is to keep reference of the parent nodes.

public class TreeNode {
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        value = x;
    }
}

public static TreeNode createTree(List<Integer> values) {
   // ???
   // return the root node
}

I feel a stupid asking this.

PS: I wondered how the tree was built from the inputs https://leetcode.com/problems/sum-root-to-leaf-numbers/

PS2 : Berto99 gave a draft of recursive way. Wondering about the iterative way (which will need to keep references of parent nodes)

How do you store null value to int value?

user4910279
– user4910279

2020-07-02 23:15:30 +00:00
Commented Jul 2, 2020 at 23:15 — user4910279
– user4910279, Commented Jul 2, 2020 at 23:15

Alberto · Accepted Answer · 2020-07-02 22:16:17Z

1

Taking an inspiration from the heaps:

public static TreeNode createTree(List<Integer> values, int index) {
   TreeNode tree = new TreeNode(values[index]);
   if(index * 2 < list.size())
       tree.left = createTree(values, index * 2);
   if(index * 2 + 1 < list.size())
       tree.right = createTree(values, index * 2 + 1);
   return tree;
}

Keep in mind that this works with the index that starts from 1, if you want the version that start from 1, you should use

public static TreeNode createTree(List<Integer> values, int index) {
   TreeNode tree = new TreeNode(values[index-1]); //   <<--- changed here
   if(index * 2 < list.size())
       tree.left = createTree(values, index * 2);
   if(index * 2 + 1 < list.size())
       tree.right = createTree(values, index * 2 + 1);
   return tree;
}

the logic is pretty simple, given an array, the root is the first element, the left child the pos*2 and the right the left child the pos*2 + 1 (again, first = 1, not 0)

answered Jul 2, 2020 at 22:16

Alberto

13.1k3 gold badges31 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Alberto Over a year ago

hoping that the code works, i've not wrote Java code in a while ahah

Raymond Chenon Over a year ago

I get the idea, the indexes are iterated by recursion ( not in a loop). Then, to initialise TreeNode root = createTree(values,1);

Alberto Over a year ago

@RaymondChenon exactly

Raymond Chenon · Accepted Answer · 2020-07-04 15:10:10Z

@Berto99 gave the main idea

Visualize the tree with inputs [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

             0
        /          \
      1             2
    /   \         /    \
  3       4      5       6 
 / \    /  \    /  \    /  \
7   8  9   10  11  12  13  14

Substitute the value 3 by index then you can infer the recurrence for left and right node.
node(3).left = 7 = 2 * index + 1
node(3).right = 8 = 2 * index + 2

The complete fine-tuned code is

    public static TreeNode createTree(List<Integer> values) {
        if (values == null || values.size() == 0) return null;
        TreeNode root = createTree(values, 0);
        return root;
    }

    private static TreeNode createTree(List<Integer> values, int index) {
        if (index >= values.size()) return null;

        Integer value = values.get(index);
        if (value == null) return null;

        TreeNode tree = new TreeNode(value);

        // tree(index).left = 2 * index + 1
        tree.left = createTree(values, index * 2 + 1);

        // tree(index).right = 2 * index + 2
        tree.right = createTree(values, index * 2 + 2);

        return tree;
    }

Collectives™ on Stack Overflow

Construct a binary tree from a sequence of values

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related