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 !!
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;
}