Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Validate a BST (Main Thread)

Here is the interview question prompt, presented for reference.

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

    5 
   / \ 
  3   9 
 / \
1   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:

class Node {
    constructor(val) {
        this.value = val;
        this.left = null;
        this.right = null;
    }
}

The method may be called like the following:

root = new Node(5);
root.left = new Node(3);
root.right = new Node(9);

console.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

You can see the full challenge with visuals at this link.

Challenges • Asked over 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Validate a BST.