Valid Binary Search Tree - Depth First Search / Binary Search Tree

The solution does not seem to work when there are duplicate nodes in the tree. Testing with [2, 2, 2] tree will return false.

Has nobody else noticed the boilerplate go buildtree func is broken… corrected below

func buildTree(nodes []string, pos *int) *Node {
val := nodes[*pos]
if val == “x” {
return nil
v, _ := strconv.Atoi(val) //need to use value here, note *pos since you incremented pos already
left := buildTree(nodes, pos)
right := buildTree(nodes, pos)
return &Node{v, left, right}

A binary search key cannot have duplicate keys.

solution using Integer (which gets around cases where a node has the MAX or MIN value):

public static boolean validBst(Node<Integer> root) {
    return validBstHelper(root, null, null);

private static boolean validBstHelper(Node<Integer> root, Integer min, Integer max) {
    if (root == null) return true;
    if (min != null && root.val < min) return false;
    if (max != null && root.val > max) return false;
    return validBstHelper(root.left, min, root.val) && validBstHelper(root.right, root.val, max);

It works with duplicates, but you have to put the null nodes (leaf nodes) as well in the custom input. so for this case custom input should be “2 2 x x 2 x x”

Can someone please let me know why I fail test 1 (and maybe also, why I fail test 5)? And how can I fix it?

def valid_bst(root: Node) → bool:

def bst(node, node_parent):

    if not node:
        return True

    if root.val < root.left.val or root.val < node_parent:
        return False
    elif root.val > root.right.val or root.val > node_parent:
        return False
    if root.val >= root.left.val:
        return bst(node.left, node)
    if root.right <= root.right.val:
        return bst(node.right, node)
    return True

return bst(root, -math.inf)

passing the parent value down isn’t good enough. In the example where there is an 8 at the bottom, this 8 is ok to be the right of 4. However, at the root, there is a 6. This 8 cannot be on the left subtree from that 6 node. You need to maintain a current allowed max and current allowed min for all nodes within a subtree to follow. If you go left, enforce a new maximum value, if you go right, enforce a new minimum value.

I think it’s worth mentioning that inorder traversal of BST is always sorted

I thought that BST has to have node.left < node < node.right. Why then does test #5 say that a tree consisting of all 7’s is a valid BST?

the condition given is: left <= curr <= right

function validBst(root) {
if (root === null) return true;

function dfs(node, min, max) {
    if (node === null) return true;
    if (node.val < min || node.val > max) return false;
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);

return dfs(root, -Infinity, Infinity);


so at first I had if (root === null) return false; bcuz I thought it a root doesn’t exist it should be “false”, but I failed a test so I changed it to “true”?! Am I off?! If the root doesn’t exist in the beginning its true?!

This took me more than 4 hours. Keep going !!

1 Like

good luck bro.

Can you please explain test #5 for Python -

7 7 7 x x x 7 x 7 x x
expected output: True

Why is this stating that BST’s can have duplicate values in them? Am I missing something?

But then they would need to state this is validating a BT, not a BST. They’ve violated the definition of what a BST is

I don’t understand as well why test #5 -

7 7 7 x x x 7 x 7 x x expected output: True

BSTs can be defined in a variety of ways from left subtree < root < right subtree, left subtree <= root < right subtree, left subtree <= root <= right subtree. This is why it’s important to gather the requirements in an interview setting to make sure you are answering the definition of a BST they are looking for because those differences will impact your answer.

Structured Programming JS Solution:

function validBst(root, min = -Infinity, max = Infinity) {
    let result = true;
    if (root) {
         result = root.val >= min && root.val <= max
             ? validBst(root.left, min, root.val) && validBst(root.right, root.val, max)
             : false;
    return result;