code-problems/solutions/javascript/binary-search-tree.js at master · blakeembrey/code-problems · 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
var root,
  createNode,
  add,
  search,
  addSubNode,
  findRightMost,
  replaceNodeInParent,
  binaryTreeDelete; // not overwrite keyword.

createNode = function createNode(num) {
  return {
    add: add,
    search: search,
    delete: binaryTreeDelete,
    left: undefined,
    right: undefined,
    value: num
  };
};

addSubNode = function(node, direct, num) {
  if (node[direct] === undefined) {
    node[direct] = createNode(num);
  } else {
    node[direct].add(num);
  }
};

add = function(num) {
  // Add the value to the correct side of the binary search tree.
  // If the value is the same as the current node, we'll just ignore it.
  if (this.value === undefined) {
    this.value = num;
  } else {
    if (num < this.value) {
      addSubNode(this, 'left', num);
    } else if (num > this.value) {
      addSubNode(this, 'right', num);
    }
  }
  return root;
};

search = function(num) {
  if (num === this.value) {
    return this;
  } else if (num < this.value && this.left) {
    return this.left.search(num);
  } else if (num > this.value && this.right) {
    return this.right.search(num);
  } else {
    return false;
  }
};

findRightMost = function(node) {
  if (node.right === undefined) {
    return node;
  }
  return findRightMost(node.right);
};

replaceNodeInParent = function(node, parent, newNode) {
  // root's parent is undefined.
  if (parent === undefined) {
    if (newNode) {
      root.value = newNode.value,
      root.left = newNode.left,
      root.right = newNode.right;
    }else{
      root.value=undefined;
    }
    return;
  }

  if (parent.left === node) {
    parent.left = newNode;
  } else {
    parent.right = newNode;
  }
};


binaryTreeDelete = function(num, parent) {
  var successor;
  if (num < this.value) {
    return this.left ? this.left.delete(num, this) : root;
  } else if (num > this.value) {
    return this.right ? this.right.delete(num, this) : root;
  } else {
    // delete key here
    if (this.left !== undefined && this.right !== undefined) {
      successor = findRightMost(this.left);
      this.value = successor.value;
      this.left.delete(successor.value, this);
    } else if (this.left) {
      replaceNodeInParent(this, parent, this.left);
    } else if (this.right) {
      replaceNodeInParent(this, parent, this.right);
    } else {
      replaceNodeInParent(this, parent); // replace with undefined
    }
  }
  return root;
};

module.exports = (root = createNode(undefined));