LeetCode: Validate Binary Search Tree Solution

Traverse in-order and validate the traversed result

Approach (In-Order Traversal)

If the result of in-order traversal is a incremental array, then it is a binary search tree

Implementation

1var isValidBST = function (root) {
2 let inOrderTraversalOutput = []
3
4 const inOrderTraversal = node => {
5 if (!node) return
6
7 inOrderTraversal(node.left)
8 inOrderTraversalOutput.push(node.val)
9 inOrderTraversal(node.right)
10 }
11
12 inOrderTraversal(root)
13
14 for (let i = 1; i < inOrderTraversalOutput.length; i++) {
15 if (inOrderTraversalOutput[i - 1] >= inOrderTraversalOutput[i]) {
16 return false
17 }
18 }
19
20 return true
21}

Approach (Recursion)

Traverse the tree updated max, min of each half

Implementation

1var isValidBST = function (root) {
2 const recursion = (
3 node,
4 minLeft = Number.NEGATIVE_INFINITY,
5 maxRight = Number.POSITIVE_INFINITY
6 ) => {
7 if (!node) return true
8
9 const cond1 = minLeft < node.val && node.val < maxRight
10 const cond2 = recursion(node.left, minLeft, node.val)
11 const cond3 = recursion(node.right, node.val, maxRight)
12
13 return cond1 && cond2 && cond3
14 }
15
16 return recursion(root)
17}

References

Original problem

Comments

Loading comments...

Tags

leetcode

tree

binary tree

Next Post

LeetCode: Number of Islands

To be consistent, first find out how to make it easy

Previous Post

HoningJS

Search Posts