Mark As Completed Discussion

Good morning! Here's our prompt for today.

Given a binary search tree like the one below, can you write a function that will return true if it is valid?

Description
SNIPPET
1    5 
2   / \ 
3  3   9 
4 / \
51   4

Recall that a BST is valid only given the following conditions:

  • The left child subtree of a node contains only nodes with values less than the parent node's.
  • The right child subtree of a node contains only nodes with values greater than the parent node's.
  • Both the left and right subtrees must also be BSTs.

You can assume that all nodes, including the root, fall under this node definition:

JAVASCRIPT
1class Node {
2	constructor(val) {
3		this.value = val;
4		this.left = null;
5		this.right = null;
6	}
7}

The method may be called like the following:

JAVASCRIPT
1root = new Node(5);
2root.left = new Node(3);
3root.right = new Node(9);
4
5console.log(isValidBST(root));

Constraints

  • Length of the given tree <= 100000
  • The nodes in the tree will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(logn) or O(d) where d is the depth of the tree

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?