# 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]
*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;
}
``````