Skip to content

Instantly share code, notes, and snippets.

@WennderSantos
Created December 16, 2018 17:54
Show Gist options
  • Save WennderSantos/a610b1e252e8949fd947007162c62128 to your computer and use it in GitHub Desktop.
Save WennderSantos/a610b1e252e8949fd947007162c62128 to your computer and use it in GitHub Desktop.
Check if a binary tree is a binary search tree
class Node
{
public Node(int data) => Data = data;
public int Data { get; }
public Node Left { get; set; }
public Node Rigth { get; set; }
public void Add(int value)
{
if (value < Data)
{
if (Left is null)
Left = new Node(value);
else
Left.Add(value);
}
else
{
if (Rigth is null)
Rigth = new Node(value);
else
Rigth.Add(value);
}
}
public bool IsBST() => IsBST(this, int.MinValue, int.MaxValue);
bool IsBST(Node node, int min, int max)
{
if (node is null)
return true;
if (node.Data < min || node.Data > max)
return false;
return IsBST(node.Left, int.MinValue, node.Data) && IsBST(node.Rigth, node.Data + 1, int.MaxValue);
}
}
class Program
{
static void Main(string[] args)
{
var root = new Node(60);
root.Add(50);
root.Add(55);
root.Add(40);
root.Add(65);
root.Add(63);
root.Add(67);
Console.WriteLine(root.IsBST());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment