Above logic fails when input is [2,2,2]
Did this a totally different way… (which in hindsight is more complex)… Did an in order traversal, saved the output to a list. Then checked that the list was sorted
public static boolean validBstUsingList(TreeNode<Integer> root){
ArrayList<Integer> list = new ArrayList<>();
captureOrderedTraversal(root, list);
return orderedList(list);
}
private static boolean orderedList(List<Integer> list){
boolean validBst = true;
Iterator<Integer> itr = list.iterator();
if(itr.hasNext()) {
Integer current, previous = itr.next();
while (itr.hasNext()) {
current = itr.next();
if (previous.compareTo(current) > 0) validBst = false;
previous = current;
}
}
return validBst;
}
public static void captureOrderedTraversal(TreeNode<Integer> node, List<Integer> list){
if(node != null){
captureOrderedTraversal(node.left, list);
list.add(node.val);
captureOrderedTraversal(node.right, list);
}
}
Any solution for that?
The dfs function gets called on each node once. So why is the total traversal O(2n - 1)? I’m referring to this line before the code implementation: “There are n nodes and n - 1 edges in a tree so if we traverse each once then the total traversal is O(2n - 1) which is O(n).” We do visit the null children of the leaf nodes, but that’s not really related to the edges of the tree, is it?
Had the same idea. It can be done without the use of a list though. Just return the node value and compare to current node:
int dfs(Node root) {
int *prev = &root->val;
if (root->left)
prev = dfs(root->left);
if (prev && *prev > root->val)
return nullptr;
if (prev && root->right)
prev = dfs(root->right);
return prev;
}
bool valid_bst(Node* root) {
if (!root) return true;
return dfs(root) != nullptr;
}
[2,2,2] is not a valid input; leaf nodes need to have null children nodes marked by x x
What if the root of BST is Integer.MIN_VALUE or Integer.MAX_VALUE, or a leaf node , we can still have a valid tree with that combination.
So below condition in given solution will give a false negative?
if (!(min < root.val && root.val < max)) {
return false;
}
Typo: “substree”
Test #6 the image is confusing because it seems that the tree is all left leaning nodes as follows starting from the root: 6 → 5 → 4. It looks like a linked list from the image but in reality it is root: 6, left node 5, right node 4. That matches the answer but the image does not. Please change.
I think based on this from the problem, there should not be duplicate values:
an inorder traversal of a binary search tree yields a list of values that is monotonically increasing (strictly increasing).
def valid_bst(root: Node) -> bool:
def dfs(node):
if not node:
return True, float("inf"), -float("inf")
is_left_valid, min_left, max_left = dfs(node.left)
is_right_valid, min_right, max_right = dfs(node.right)
is_cur_valid = node.val > max_left and node.val < min_right
max_val = max(max_left, node.val, max_right)
min_val = min(min_right, node.val, min_left)
return is_cur_valid and is_left_valid and is_right_valid, min_val, max_val
is_valid, _, _ = dfs(root)
return is_valid
The problem statement should note that the node values are numbers. At least in JS, it is not sufficient to set min and max to the smallest & largest numerical values if the node values could be, for instance, strings.
console.log('a' < Number.INFINITY)
console.log('a' > Number.INFINITY)
Both return false. You’d have to pass different min and max values depending on the node value types.
The solution in C++ seems to failed with this test case 2147483647 2147483646 x x x.
Found solution.
#include <optional>
...
bool dfs(Node<int>* node, std::optional<int> min_val, std::optional<int> max_val) {
if (!node) return true;
if (min_val.has_value() && node->val <= min_val) return false;
if (max_val.has_value() && node->val >= max_val) return false;
return dfs(node->left, min_val, node->val) && dfs(node->right, node->val, max_val);
}
bool valid_bst(Node<int>* root) {
return dfs(root, std::nullopt, std::nullopt);
}
I think the test case 6 5 x 4 x x x should be true, not false.
The graph doesn’t make it obvious (since the nodes are in a straight line), but based on my understanding of how the input string (6 5 x 4 x x x) is deserialized into a tree, the 5 node has a null left child, and a right child of 4, which would make an invalid BST.