Created
June 5, 2020 19:13
-
-
Save hungrypc/5ce6972f032bf0a05f51d03e40eae340 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| class Node { | |
| constructor(val) { | |
| this.val = val | |
| this.left = null | |
| this.right = null | |
| } | |
| } | |
| const array = [1, 3, 4, 6, 7, 8, 9, 11, 13, 15, 20, 27, 30, 38, 40] | |
| function constructBST(arr) { | |
| if (arr.length <= 1) { | |
| if (arr[0]) return new Node(arr[0]) | |
| else return null | |
| } | |
| const middle = Math.floor(arr.length / 2) | |
| const node = new Node(arr[middle]) | |
| node.left = constructBST(arr.slice(0, middle)) | |
| node.right = constructBST(arr.slice(middle + 1)) | |
| return node | |
| } | |
| const tree = constructBST(array) | |
| console.log(tree) | |
| function validate(root) { | |
| const stack = [] | |
| stack.push({ | |
| node: root, | |
| upperBound: Number.POSITIVE_INFINITY, | |
| lowerBound: Number.NEGATIVE_INFINITY | |
| }) | |
| while (stack.length) { | |
| const { node, upperBound, lowerBound } = stack.pop() | |
| if (node.val <= lowerBound || node.val >= upperBound) return false | |
| if (node.left) { | |
| stack.push({ | |
| node: node.left, | |
| upperBound: node.val, | |
| lowerBound | |
| }) | |
| } | |
| if (node.right) { | |
| stack.push({ | |
| node: node.right, | |
| upperBound, | |
| lowerBound: node.val | |
| }) | |
| } | |
| } | |
| return true | |
| } | |
| console.log(validate(tree)) | |
| function findLargest(root) { | |
| let current = root | |
| while (current.right) { | |
| current = current.right | |
| } | |
| return current.val | |
| } | |
| console.log(findLargest(tree)) | |
| function findSecondLargest(root) { | |
| let current = root | |
| while (current) { | |
| if (!current.right && current.left) { | |
| return findLargest(current.left) | |
| } else if (current.right && !current.right.left && !current.right.right) { | |
| return current.val | |
| } | |
| current = current.right | |
| } | |
| } | |
| console.log(findSecondLargest(tree)) | |
| function isBalanced(root) { | |
| const stack = [] | |
| const depths = [] | |
| stack.push([root, 0]) | |
| while (stack.length) { | |
| const [ node, depth ] = stack.pop() | |
| if (!node.left && !node.right) { | |
| if (!depths.includes(depth + 1)) { | |
| depths.push(depth + 1) | |
| if (depths.length > 2 || (depths.length === 2 && Math.abs(depths[0] - depths[1]) > 1)) return false | |
| } | |
| } | |
| if (node.left) stack.push([node.left, depth + 1]) | |
| if (node.right) stack.push([node.right, depth + 1]) | |
| } | |
| return true | |
| } | |
| console.log(isBalanced(tree)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment