1

How to create a Full Binary Tree from an array of Node?

The input is an array of node:

const arr1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4];
const arr2 = [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8];

The image of the tree be like below:

enter image description here

The output is a Tree Structure as below:

const expectedOutput = {
  val: 3,
  left: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 2,
      left: { val: 7, left: null, right: null },
      right: { val: 4, left: null, right: null },
    },
  },
  right: {
    val: 1,
    left: {
      val: 9,
      left: null,
      right: null,
    },
    right: {
      val: 8,
      left: null,
      right: null,
    },
  },
};

So far I tried with the program below, but it didn't return the expected Output above.

const arr1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4];
const arr2 = [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8];

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

function createTree(arr, rootIndex = 0, childIndex = 0) {
  if (arr[rootIndex] === null) {
    return null;
  } else if (childIndex + 1 < arr.length) {
    childIndex++;
    const leftChildIndex = childIndex;
    childIndex++;
    const rightChildIndex = childIndex;
    return new TreeNode(
      arr[rootIndex],
      createTree(arr, leftChildIndex, childIndex),
      createTree(arr, rightChildIndex, childIndex)
    );
  } else {
    return new TreeNode(arr[rootIndex], null, null);
  }
}

const output = createTree(arr1);

console.log(output);

Improve this question
3
  • What's your actual question or problem? Commented Jun 30, 2021 at 15:28
  • 1
    "I have an issue to pass the childIndex properly" What kind of issue? Commented Jun 30, 2021 at 15:39
  • Does this answer your question? How to make binary tree from array in javascript? Commented Jun 30, 2021 at 21:14

2 Answers 2

Reset to default
4

You could push the targets to an array and take the target of the same index for a new node.

The following approach maintains a small data set without having properties with null values.

If this is not wanted, just change the constructor to add null to left and right.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null
    }
}


class Node {
    constructor(value) {
        this.value = value;
    }
}

function createTree(data) {
    const targets = [[]];
    let head;
        
    data.forEach((value, i) => {
        const
            node = new Node(value),
            [target, side] = targets[i];

        targets.push([node, 'left'], [node, 'right']);

        if (!target) head = node;
        else if (value !== null) target[side] = node;        
    });

    return head;
}

console.log(createTree([3, 5, 1, 6, 2, 9, 8, null, null, 7, 4]));
console.log(createTree([3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8]));
.as-console-wrapper { max-height: 100% !important; top: 0; }

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

5 Comments

Thanks for your answer. I actually want to use this approach by looping the array one by one, But I cannot figure out how to to do it. The reason I want to make at least one left and right leaves node because I want to have a full binary tree and I updated my title for this.
what do you mean by looping "one by one"?
Simple for loop in the array. such as array.forEach(). But I don't how to do it in this way. Therefore, I am happy to see your answer. Another answer is like jumping the index wiht 2*i+1 with recursive.
i use a forEach ...? what should i change?
Your answer is good, nothing to change.
3

For a node at index i in your array, the index of its left child is 2 * i + 1 and the index of its right child is 2 * i + 2. Armed with this knowledge, we can write:

const arr1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4];


const nullify = x => (typeof x === 'undefined' || x.val === null) ? null : x;
let result = arr1.map(val => ({ val })).map((obj, i, array) => Object.assign(obj, {
  left: nullify(array[2 * i + 1]),
  right: nullify(array[2 * i + 2])
}))[0];



console.dir(result, { depth: null });

Improve this answer

2 Comments

Thanks for your answer. It really inspires me because I struggle a lot to get the child index properly. Thanks again!
@Wyck, impressing code size :) Like it! Although the time complexity of this is O(n) because we iterates incoming array just twice, we can make little improvement by slicing second iteration by arr1.slice(0, arr1.length / 2 + 2) or by early return if using usual "for" loop. Of course, it won't change the weather )

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.