leetcode-javascript/solutions/0919-complete-binary-tree-inserter.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Complete Binary Tree Inserter
 * Time Complexity: O(N)
 * Space Complexity: O(N)
 */
var CBTInserter = function (initialRoot) {
  this.rootNode = initialRoot;
  this.parentCandidates = [];

  const bfsLevelQueue = [initialRoot];
  let queueIndex = 0;

  while (queueIndex < bfsLevelQueue.length) {
    const activeNode = bfsLevelQueue[queueIndex];

    if (!activeNode.left || !activeNode.right) {
      this.parentCandidates.push(activeNode);
    }

    if (activeNode.left) {
      bfsLevelQueue.push(activeNode.left);
    }
    if (activeNode.right) {
      bfsLevelQueue.push(activeNode.right);
    }

    queueIndex++;
  }
};

CBTInserter.prototype.insert = function (newVal) {
  const newNodeToAdd = new TreeNode(newVal);
  const targetParentNode = this.parentCandidates[0];

  let parentNodeValue;

  if (targetParentNode.left === null) {
    targetParentNode.left = newNodeToAdd;
    parentNodeValue = targetParentNode.val;
  } else {
    targetParentNode.right = newNodeToAdd;
    parentNodeValue = targetParentNode.val;
    this.parentCandidates.shift();
  }

  this.parentCandidates.push(newNodeToAdd);
  return parentNodeValue;
};

CBTInserter.prototype.get_root = function () {
  return this.rootNode;
};