BST Validate Coding Interview Question | Skilled.dev
Interview Question

BST Validate

Given the root node of a binary tree, write a function isBST that returns a boolean if the binary tree is also a valid binary search tree.

  • You can assume the tree won't be empty
  • The tree will not contain duplicate values
 

The nodes in the tree will be standard binary nodes:

 

Breakdown

Loading...

Table of Contents

Validate My Answer

  1. There are different iterative and recursive solutions that all have the same time and space complexity. Feel free to approach it in whichever way you feel most comfortable, and I'll provide both an iterative and recursive approach in my solution.

  2. For a binary search tree, ALL the descendants to the left of a node are smaller, and ALL the descendants to the right of a node are larger. You must ensure that a node is not only correct for its immediate parent, but also all of the ancestors.

  3. The worst-case Big O time and space solution in both the iterative and recursive case are O(n) where n is the number of nodes in the tree.

Loading...

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {BinaryNode} root
 * @return {bool}
 */
const isBST = (root) => {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access

BST Validate

Given the root node of a binary tree, write a function isBST that returns a boolean if the binary tree is also a valid binary search tree.

  • You can assume the tree won't be empty
  • The tree will not contain duplicate values
 

The nodes in the tree will be standard binary nodes:

 
/**
 * @param {BinaryNode} root
 * @return {bool}
 */
const isBST = (root) => {
  // Your solution here
}
// Upgrade for full course access
// Upgrade for full course access