Skip to content

Instantly share code, notes, and snippets.

@misterpoloy
Created September 6, 2021 22:07
Show Gist options
  • Save misterpoloy/ec9f54c43263864004c6f8e780b15139 to your computer and use it in GitHub Desktop.
Save misterpoloy/ec9f54c43263864004c6f8e780b15139 to your computer and use it in GitHub Desktop.
Return if a tree is balanced, difference is not greater than 1 in javascript
// Return Node info
function getNodeHeightBalanced(tree) {
if (tree === null) return { isBalanced: true, height: -1}
const leftTreeInfo = getNodeHeightBalanced(tree.left)
const rightTreeInfo = getNodeHeightBalanced(tree.right)
const isBalanced = (
// Both left and right sub-tree should be balanced
(leftTreeInfo.isBalanced && rightTreeInfo.isBalanced) &&
// Difference should not be longer than 1
Math.abs(leftTreeInfo.height - rightTreeInfo.height) < 2
)
const currentHeight = Math.max(leftTreeInfo.height, rightTreeInfo.height) + 1
return ({ isBalanced, height: currentHeight })
}
function heightBalancedBinaryTree(tree) {
// Write your code here.
return getNodeHeightBalanced(tree).isBalanced;
}
@misterpoloy
Copy link
Author

time and space complexicity of a balanced tree

gist

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment