One Pager Cheat Sheet
- Write a function,
isValidBST(node)
, that returnstrue
if the given binary search tree is valid according to the defined conditions. - The left subtree of a node in a Binary Search Tree (BST) must only contain nodes with keys LESS than the node's key, while the right subtree must contain nodes with keys GREATER than the node's key to maintain its in-order traversal which produces an increasing order of nodes.
- The In-order traversal of a Binary Search Tree follows a specific algorithm to access data in a very efficient manner, visiting each node left to right by recursively calling the
Inorder()
function. - An in-order traversal of a
BST
processes the node keys in ascending order by beginning at the smallest key and progressively traversing rightward. - The given recursive function will
return
2 times the result of the recursive call until the if statement evaluates toTrue
, in which case thevalue
ofn
isreturned
, which in the example is4
and the result offunc(2)
is16
. Running through inputs with a binary search tree can help trigger insights for a solution.
- Checking if every left child is smaller than the root, and every right child is greater than the local root is a
brute force
solution for determining the direction of nodes in a tree. - We can
recursively
check every subtree by running through the method, but to ensure accuracy we should extend the tree by adding two more children to the root's left child. - We can use an
in-order depth-first search
to check abinary search
tree for validity by comparing its processed node values in sorted order. - We can determine if a given tree is valid in
O(n)
time complexity andO(logn)
space complexity by iterating through alln
elements and checking that each successive element is greater than the previous iteration.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
85
}
var assert = require('assert');
​
function isValidBST(root) {
const searchResults = [];
inOrder(root, searchResults);
​
for (let i = 1; i < searchResults.length; i++) {
if (searchResults[i - 1] >= searchResults[i]) {
return false;
}
}
​
return true;
}
​
function inOrder(root, output) {
if (!root) {
return;
}
​
inOrder(root.left, output);
output.push(root.val);
inOrder(root.right, output);
}
​
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
​
// Regular binary trees
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.