Last active
August 17, 2016 00:09
-
-
Save pzaich/7f7cb4378c584a0dc6a061e105d1d37b to your computer and use it in GitHub Desktop.
Is a given a binary tree superbalanced? A simple Javascript traversal of binary trees
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// First Build binary trees from a pojo representation | |
// Find the max depths of the binary tree's "node leafs" | |
var _ = require('underscore'); | |
function BinaryTreeNode(value) { | |
this.value = value; | |
this.left = null; | |
this.right = null; | |
} | |
BinaryTreeNode.prototype.insertLeft = function(value) { | |
this.left = new BinaryTreeNode(value); | |
return this.left; | |
}; | |
BinaryTreeNode.prototype.insertRight = function(value) { | |
this.right = new BinaryTreeNode(value); | |
return this.right; | |
}; | |
var config = { | |
value: 0, | |
left: { | |
value: 1, | |
left: { | |
value: 2, | |
right: { | |
value: 3, | |
left: { | |
value: 4 | |
} | |
} | |
} | |
}, | |
right: { | |
value: 1 | |
} | |
} | |
function buildTree(object) { | |
if (typeof object === "undefined") return undefined; | |
var parentNode = new BinaryTreeNode(object.value); | |
parentNode.value = object.value; | |
parentNode.left = buildTree(object.left); | |
parentNode.right = buildTree(object.right); | |
return parentNode; | |
} | |
var tree = buildTree(config); | |
function depthSeparation (depths) { | |
var min = depths[0]; | |
var max = depths[0]; | |
depths.forEach(function (depth) { | |
if (depth < min) { | |
min = depth; | |
} | |
if (depth > max) { | |
max = depth; | |
} | |
}); | |
return max - min; | |
} | |
function isSuperBalanced(tree) { | |
var depths = []; | |
function traverse(node, depth) { | |
if (typeof depth === "undefined") depth = 0; | |
var children = _.compact([node.right, node.left]) | |
if (children.length > 0) { | |
depth += 1; | |
children.forEach(function (child) { | |
traverse(child, depth); | |
}); | |
} else { | |
depths.push(depth); | |
} | |
} | |
traverse(tree); | |
return depthSeparation(depths) <= 1; | |
} | |
console.log(isSuperBalanced(tree)); | |
var balancedTree = buildTree({ | |
value: 0, | |
left: { | |
value: 1 | |
}, | |
right: { | |
value: 1 | |
} | |
}); | |
console.log(isSuperBalanced(balancedTree)); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Test max depths of a binary tree via a "breadth first" iterative approach | |
function isSuperBalancedBreadthFirst(tree) { | |
var queue = [tree]; | |
var min = 0; | |
var max = 0; | |
var depth = 0; | |
var elementsToDepthIncrement = queue.length; | |
var elementsInNextDepth = 0; | |
while (queue.length > 0) { | |
var currentNode = queue.shift(); | |
var children = _.compact([currentNode.left, currentNode.right]); | |
elementsToDepthIncrement -= 1; | |
elementsInNextDepth += children.length; | |
children.forEach(child => queue.push(child)); | |
if (!currentNode.left && !currentNode.right) { | |
if (min === 0) { | |
min = depth; | |
} | |
max = depth; | |
} | |
if (elementsToDepthIncrement === 0) { | |
depth += 1; | |
elementsToDepthIncrement = elementsInNextDepth; | |
elementsInNextDepth = 0; | |
} | |
} | |
return max - min <= 1; | |
} | |
console.log(isSuperBalancedBreadthFirst(tree)); | |
console.log(isSuperBalancedBreadthFirst(balancedTree)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment