Skip to content

Instantly share code, notes, and snippets.

@ylegall
Created November 7, 2013 20:33
Show Gist options
  • Save ylegall/7361401 to your computer and use it in GitHub Desktop.
Save ylegall/7361401 to your computer and use it in GitHub Desktop.
determine if a BST is valid
import std.stdio;
class Node
{
int val;
Node left, right;
this(int val, Node left=null, Node right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
bool isValid(Node root) {
return isValid(root, int.min, int.max);
}
bool isValid(Node root, int min, int max) {
if (root is null) return true;
if (root.val < min || root.val > max) return false;
if(!isValid(root.left, min, root.val)) return false;
if(!isValid(root.right, root.val, max)) return false;
return true;
}
void main()
{
auto root = new Node(10,
new Node(5,
new Node(3),
new Node(7)),
new Node(15,
new Node(16),
new Node(18)));
writeln(isValid(root));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment