BST Validate Coding Interview Question | Skilled.dev
Interview Question

BST Validate

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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
// Example 1:
    9
   / \
  5  22
 / \   \
1   7  30
      /
     25

isBST(root); // true

// Example 2:
    9
   / \
  5  22
 / \   \
1  10  30

isBST(root); // false
// 10 > 9 but falls under its left path

The nodes in the tree will be standard binary nodes:

class BinaryNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

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 descendents to the left of a node are smaller, and ALL the descendents to the right of a node are larger. You must ensure that a node not only is correct for the its immediate parent, but also all of the ancestors.

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