Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save spirinvladimir/3f2705387a7247381e0e70510b68f758 to your computer and use it in GitHub Desktop.
Save spirinvladimir/3f2705387a7247381e0e70510b68f758 to your computer and use it in GitHub Desktop.
function insert (node, x) {
if (x < node.value) {
if (node.left) {
if (x < node.left.value) {
insert(node.left, x)
} else {
node.left = {value: x, left: node.left}
}
} else {
node.left = {value: x}
}
} else {
if (node.right) {
if (x > node.right.value) {
insert(node.right, x)
} else {
node.right = {value: x, right: node.right}
}
} else {
node.right = {value: x}
}
}
}
function check (node) {
if (node.left) {
if (node.value - node.left.value > 1) {
return node.value - 1
}
}
if (node.right) {
if (node.right.value - node.value > 1) {
return node.value + 1
}
}
return node.left && check(node.left) || node.right && check(node.right)
}
function missingNumber(a) {
if (a.length === 1) {
return a[0] === 0 ? 1 : 0
}
var tree = {value: a[0]}
for (var i = 1; i < a.length; i++) {
insert(tree, a[i])
}
var missed = check(tree)
var node = tree
while (node.left) node = node.left
return missed === undefined
? node.value === 0
? a.length
: 0
: missed
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment