JavaScript build Incomplete Binary Tree from an array

Question

This may seem like a duplicate question but I haven't been able to find the answer for my question anywhere on SOF or elsewhere.

I'd like to build an Incomplete Binary Tree from an Array and a not null root node, in JavaScript with null value represents the null subtree, not a subtree with value = null.

Expected result:

TreeNode {
  val: 1,
  left:
   TreeNode {
     val: 2,
     left: TreeNode { val: 4, left: null, right: null },
     right: null },
  right:
   TreeNode {
     val: 3,
     left: null,
     right: TreeNode { val: 5, left: null, right: null } } }

The expected output above could be done manually like so:

const myTree = new TreeNode(1);
myTree.left = new TreeNode(2);
myTree.left.left = new TreeNode(4);
myTree.right = new TreeNode(3);
myTree.right.right = new TreeNode(5);

The tree should look like this:

Here's my code:

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    insert(values, i = 0) {
        if (i >= values.length) return;
        const queue = [this];
        while (queue.length > 0) {
            let current = queue.shift();
            if (current.left === null) {
                current.left = new TreeNode(values[i]);
                break;
            }
            queue.push(current.left);
            if (current.right === null) {
                current.right = new TreeNode(values[i]);
                break;
            }
            queue.push(current.right);
        }
        this.insert(values, i + 1);
        return this;
    }
}
(function() {
    // This builds a tree with null nodes with null values and null children.
    // The goal is to skip updating any null child
    const myTree = new TreeNode(1);
    myTree.insert2([2,3,4,null,null,5]);
    console.log(myTree);
}());

The issue here is I get a null child as a TreeNode with value = null like so:

TreeNode {
  value: 1,
  left:
   TreeNode {
     value: 2,
     left: TreeNode { value: 4, left: null, right: null },
     right: TreeNode { value: null, left: null, right: null } },
  right:
   TreeNode {
     value: 3,
     left: TreeNode { value: null, left: null, right: null },
     right: TreeNode { value: 5, left: null, right: null } } }

I can handle the children of a null node by adding:

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

but I haven't been able to add only null value instead of a full TreeNode. I've tried:

if (current.left === null) {
    current.left = values[i] !== null ? new BinaryTree(values[i]) : null;
    break;
}

Or:

if (current.left === null && values[i]) {}

Or:

if (!values[i]) return;

But none returns the expected result.

I've also looked at some solutions using Java but the answers use built-in LinkedList in Java so I'm not sure that's the right way to do in JS.

Answer to Scott Sauyet's question:

The expected result for

const myTree = new TreeNode (1); 
myTree .insert ([2,null, 4, null, 6, 7])

is:

TreeNode {
    val: 1,
    left: TreeNode {
        val: 2,
        left: TreeNode {
            val: 4,
            left: TreeNode { val: 6, left: null, right: null },
            right: TreeNode { val: 7, left: null, right: null }
        },
        right: null
    },
    right: null
}

Can you clarify? Did you mean: can the output contain 0 as a null node or Did you want me to add 0 instead of null value in my code? — Viet
– Viet, Commented Jun 5, 2020 at 17:58
no, sorry. but what should happrn, if you have no starting node? — Nina Scholz
– Nina Scholz, Commented Jun 5, 2020 at 17:59
What would be the expected behavior for const myTree = new TreeNode (1); myTree .insert ([2,null, 4, null, 6, 7])? That is, what happens if you don't create the node (3) that's supposed to be the parent of other nodes (6 and 7)? — Scott Sauyet
– Scott Sauyet, Commented Jun 5, 2020 at 18:04
@ScottSauyet: I've updated my question with the answer for your question. — Viet
– Viet, Commented Jun 5, 2020 at 18:12
@HereticMonkey I agree. However, before I have to implement another class of a LinkedList just to build a BinaryTree, I'd like to try without one first. — Viet
– Viet, Commented Jun 5, 2020 at 18:15

trincot · Accepted Answer · 2020-06-05 19:33:01Z

You did right by checking values[i] for null, and not creating a new Node when it is null, but you also need to skip that node for any subsequent value. This is difficult to do in a recursive solution, so I would suggest to make it iterative:

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    insert(values) {
        const queue = [this];
        let i = 0;
        while (queue.length > 0) {
            let current = queue.shift();
            for (let side of ["left", "right"]) {
                if (!current[side]) {
                    if (values[i] !== null) {
                        current[side] = new TreeNode(values[i]);
                    }
                    i++;
                    if (i >= values.length) return this;
                }
                if (current[side]) queue.push(current[side]);
            }
        }
        return this;
    }
}

(function() {
    const myTree = new TreeNode(1);
    myTree.insert([2,3,4,null,null,5]);
    console.log(myTree);
}());

Be aware though, that if you call myTree.insert multiple times, then the previous null nodes will be expanded with new data.

If that is undesired, then one measure you could take is to drop the insert method, and provide this functionality only via the constructor.

Or, otherwise, you first need to use the queuing mechanism to find out which are the nodes that should be extended. They are those that have not 2 children, and are not followed (in BFS order) by nodes that have children.

Here is how that could look (with a bit larger tree as demo):

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    getInsertionPoints() {
        // find uninterrupted series of leaves in BFS order
        const queue = [this];
        const leaves = [];
        while (queue.length) {
            let current = queue.shift();
            for (let side of ["left", "right"]) {
                if (current[side]) {
                    queue.push(current[side]);
                    leaves.length = 0; // reset
                } else {
                    leaves.push([current, side]);
                }
            }
        }
        return leaves;
    }
    insert(values) {
        let queue = this.getInsertionPoints();
        for (let value of values) {
            let [current, side] = queue.shift();
            if (value !== null) {
                current[side] = new TreeNode(value);
                queue.push([current[side], "left"], [current[side], "right"]);
            }
        }
        return this;
    }
}

(function() {
    const myTree = new TreeNode(1);
    myTree .insert ([2,null, 4, null, 6, 7]);
    myTree .insert ([8, null, 9, 10, 11, 12]);
    console.log(myTree);
}());

Nina Scholz · Accepted Answer · 2020-06-05 19:32:26Z

2

This is a different approach by calculating the target of a node.

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

    insert(values) {
        let size = 1,
            number = 0;

        for (let value of values) {
            if (value !== null) {
                [...(number.toString(2).padStart(size, 0))].reduce((node, index, i, { length }) => {
                    let side = ['left', 'right'][index];
                    if (node[side] === null) {
                        node[side] = new TreeNode(i + 1 === length ? value : 'missing');
                    }
                    return node[side];
                }, this);
            }
            number++;
            if (number === 1 << size) {
                size++;
                number = 0;
            }
        }
    }
}

const myTree = new TreeNode(1);
myTree.insert([2, 3, 4, null, null, 5]);

console.log(myTree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jun 5, 2020 at 19:32

answered Jun 5, 2020 at 18:53

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

1 Comment

trincot Over a year ago

Note that this does not produce the desired result for the second example that the OP added to their question.

Gershom Maes · Accepted Answer · 2020-06-05 19:26:34Z

I would redesign the insert function so that it recursively calls insert on children instances, not the parent.

If an example Array contains 15 elements, then it has values at indices 0-14. We have a mapping between index and position-in-tree. Here is how indices map to a complete tree with 15 nodes:

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

When we tell the root node, #0, to .insert([ 'a', 'b', 'c', 'd', 'e', 'f', ... ]) we know that node #1 gets the value at index 0 ('a'), #2 gets the value at index 1 ('b'), etc. Node #1 gets index 0, node #2 gets index 1, node #3 gets index 2... the pattern is that index n is the value for node #n + 1. This is because index 0 doesn't refer to the root node but rather the left child of the root node.

There is a relationship between the index of a parent node, and the indices of its children nodes. We could call this getChildIndices(parIndex):

getChildIndices(0) = [ 1, 2 ];
getChildIndices(1) = [ 3, 4 ];
getChildIndices(2) = [ 5, 6 ];
getChildIndices(3) = [ 7, 8 ];
getChildIndices(4) = [ 9, 10 ];
getChildIndices(5) = [ 11, 12 ];
getChildIndices(6) = [ 13, 14 ];
.
.
.

Because this mapping you've chosen has a certain elegance, the function is very simple:

let getChildIndices = parIndex => [ parIndex * 2 + 1, parIndex * 2 + 2 ];

With this we can write a more elegant insert function:

let getChildIndices = parInd => [ parInd * 2 + 1, parInd * 2 + 2 ];

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  insert(values, myInd=0) {
    
    let [ lInd, rInd ] = getChildIndices(myInd);
    
    let vals = [
      { ind: lInd, prop: 'left' }, // `lInd` corresponds to our "left" property
      { ind: rInd, prop: 'right'}  // `rInd` corresponds to our "right" property
    ];
    
    for (let { ind, prop } of vals) {
      
      // If we're out-of-bounds in `values`, stop!
      if ((ind - 1) >= values.length) continue;
      
      // A value of `null` in `values` indicates the subtree is null. Otherwise, a child
      // node exists.
      let shouldNodeExist = values[ind - 1] !== null;
      
      if (this[prop] && !shouldNodeExist) { // If the node exists and shouldn't...
        
        // Set the node to null
        this[prop] = null;
        
      } else if (!this[prop] && shouldNodeExist) { // If the node doesn't exist and should...
        
        // Create a new child node
        this[prop] = new TreeNode(null);
        
      }
      
      // Recursively call insert on the new child node, informing it of its index
      if (this[prop]) {
        this[prop].value = values[ind - 1];
        this[prop].insert(values, ind);
      }
      
    }
      
  }
}

let tree1 = new TreeNode(1);
tree1.insert([ 2, 3, 4, null, null, 5 ]);
console.log({ tree1 });

let tree2 = new TreeNode(1); 
tree2.insert([ 2, null, 4, null, 6, 7 ]);
console.log({ tree2 });

Note that this insert method allows adding, modifying, and deleting nodes from the tree. Any index containing null will cause its corresponding subtree to be deleted.

Note that if we try to specify discontiguous subtrees with this method - e.g. we specify values at indices 3 and 4, but null at their parent index (1), the entire subtree at index 1 will be null, and indices 3 and 4 will be ignored.

While this is an interesting approach, it doesn't handle the second case the way it was requested. ==> (1 (2 (4 (6 (null, null)), (7 (null, null)), null), null)

Scott Sauyet · Accepted Answer · 2020-06-05 21:10:16Z

Update

This can be made much cleaner with a dedicated breadth-first traversal function (bft.)

const bft = (nodes) => 
  nodes .length == 0
    ? []
    : [
        ...nodes, 
        ...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
      ] 

class TreeNode {
  constructor (val) {
    this.val = val
  }
  insert (vals) {
    return vals.reduce ((
      tree, val, _, __,
      parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
    ) => 
      ((parent [parent.left === void 0 ? 'left' : 'right'] = val === null 
        ? null 
        : new TreeNode(val)),
      tree), 
    this)
  }
}

You can see this approach in the following snipped:

const bft = (nodes) => 
  nodes .length == 0
    ? []
    : [
        ...nodes, 
        ...bft(nodes.flatMap (n => n .left ? n.right ? [n.left, n.right] : [n.left] : []))
      ] 

class TreeNode {
  constructor (val) {
    this.val = val
  }
  insert (vals) {
    return vals.reduce ((
      tree, val, _, __,
      parent = bft([tree]) .find (n => n.left === void 0 || n.right === void 0) || {}
    ) => 
      ((parent [parent.left === void 0 ? 'left' : 'right'] = val === null 
        ? null 
        : new TreeNode(val)),
      tree), 
    this)
  }
}


let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);

// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);

// Handles blocked nodes
myTree = new TreeNode(1); 
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);

// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);

.as-console-wrapper {min-height: 100% !important; top: 0}

Original Answer

One other possibility makes a different trade-off than most of the answers here.

Most other answers allow a single insert, which at that point might as well fold into the constructor.

This one allows multiple inserts. But it does not set left and right children to null unless we actually include a null in the values to insert. So some nodes have only a val, some have a val and left, and the others have a val, a left and a right. By leaving these holes, we keep the places for additional nodes to be added later.

This technique also fairly gracefully handles the case when everything is full, simply refusing to add the remaining nodes.

class TreeNode {
  constructor (val) {
    this .val = val
  }
  insert (vals) {
    return vals .reduce ((t, v) => {
      const queue = [t]
      while (queue .length) {
        let node = queue .shift ()
        if (node .left === void 0) {
          node .left = v === null ? null : new TreeNode(v)
          return t
        } else  if (node .right === void 0) {
          node .right = v === null ? null : new TreeNode(v)
          return t
        } else {
          if (node .left !== null) {
            queue .push (node .left)
          } 
          if (node .right !== null) {
            queue.push (node.right)
          }
        }
      }
      return t // If we hit this point, then our insert failed: there's no room left.      
    }, this)
  }
}

let myTree = new TreeNode (1);
myTree .insert ([2, 3, 4, null, null, 5]);
console .log (myTree);

// Handles subsequent inserts
myTree .insert ([6, null, null, null, 7, 8]);
console .log (myTree);

// Handles blocked nodes
myTree = new TreeNode(1); 
myTree.insert([ 2, null, 4, null, 6, 7 ]);
console.log(myTree);

// Fails (somewhat) gracefully when node cannot be inserted
myTree = new TreeNode (1);
myTree .insert ([null, null, null, 2]);
console .log (myTree);

.as-console-wrapper {min-height: 100% !important; top: 0}

We use a breadth-first traversal using a queue to hold the nodes still to visit, starting with the root, adding each non-null left and right child if we haven't already found our insertion point.

The big potential downside for this is that there is no guarantee that the left or right child of any node is actually defined. We use JS's two distinct nil values for different purposes here. null signifies that this subtree is blocked. undefined signals that while it doesn't yet exist, it's available for insertion. Some people really prefer not to distinguish these two nilary values in such a way. I think that it works with the grain of the language, but YMMV.

This is not code I'm particularly proud of. I prefer never to mutate data structure but to always create new ones. And I prefer to work with expressions over statements as much as possible. But I've spent too long on this already, so I won't spend the time now to see if I can clean it up. If nothing else, it offers a different approach than the other answers here, and solves certain problems that they don't.

kmoerman · Accepted Answer · 2020-06-05 20:31:06Z

0

Building on @trincot's iterative solution, the code below loops over the input, rather than over the queue.

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    
    insert(values) {
        // clear current children before insert
        this.left = this.right = null;

        const queue = [this];
        for (var i = 0; i < values.length; ) {
          const current = queue.shift();
          for (let side of ["left", "right"]) {
            if (i < values.length && values[i] !== null) {
              current[side] = new TreeNode(values[i]);
              queue.push(current[side]);
            }
            ++i;
          }
        }
        return this;
    }
}


const myTree = new TreeNode(1);
myTree.insert([2,3,4,null,null,5]);
console.log(myTree);

Note that you will always fill nodes from left to right, and you are going down the tree level per level (skipping nulls, as per your requirements). Deeper nodes are always newly created, and each node is only visited once. Therefore there is no need to check if either the left or right children have been set previously.

The extra check i < values.length is added, as the input array might contain an odd number of entries (missing the rightmost bottom element of the tree).

edited Jun 5, 2020 at 20:31

answered Jun 5, 2020 at 18:54

kmoerman

4401 gold badge4 silver badges14 bronze badges

4 Comments

trincot Over a year ago

Nice, but this will destroy previous content in the tree when insert is called a second time.

kmoerman Over a year ago

The question refers to building, not extending.

trincot Over a year ago

That may be so, but a second call could lead to a tree that still has some of the nodes of the first call, while others have been replaced. This is not what I would call building.

kmoerman Over a year ago

Agreed, for the top level node, thank you for sharing your concern. I have edited the code to resolve this bug.

Collectives™ on Stack Overflow

JavaScript build Incomplete Binary Tree from an array

5 Answers 5

1 Comment

1 Comment

1 Comment

Update

Original Answer

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

1 Comment

1 Comment

Update

Original Answer

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related