Create a gist now

Instantly share code, notes, and snippets.

Write a function that returns whether a given binary tree is a valid binary search tree.
/****************************************************************
Adam Lum
12/17/2012
Coding for Interviews on Binary Search Trees
http://codingforinterviews.com
Write a function that returns whether a given binary tree
is a valid binary search tree.
*******************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CodingInterviewPractice_2012_12_17
{
class Node
{
public int key;
public Node left;
public Node right;
}
class Program
{
static bool IsValidBST(Node _root)
{
bool isValid = true;
if (_root.left != null)
{
if (_root.left.key < _root.key)
{
isValid = IsValidBST(_root.left);
}
else
{
isValid = false;
}
}
if (_root.right != null && isValid)
{
if (_root.right.key > _root.key)
{
isValid = IsValidBST(_root.right);
}
else
{
isValid = false;
}
}
return isValid;
}
static void Main(string[] args)
{
// Build a valid tree
Node currentNode;
Node validTree = new Node();
validTree.key = 8;
validTree.left = new Node();
validTree.left.key = 3;
currentNode = validTree.left;
currentNode.left = new Node();
currentNode.left.key = 1;
currentNode.right = new Node();
currentNode.right.key = 6;
currentNode = currentNode.right;
currentNode.left = new Node();
currentNode.left.key = 4;
currentNode.right = new Node();
currentNode.right.key = 7;
validTree.right = new Node();
validTree.right.key = 10;
currentNode = validTree.right;
currentNode.right = new Node();
currentNode.right.key = 14;
currentNode = currentNode.right;
currentNode.left = new Node();
currentNode.left.key = 13;
// Build an ivalid tree
Node invalidTree = new Node();
invalidTree.key = 9;
invalidTree.left = new Node();
invalidTree.left.key = 3;
currentNode = invalidTree.left;
currentNode.left = new Node();
currentNode.left.key = 4;
currentNode.right = new Node();
currentNode.right.key = 7;
currentNode = currentNode.right;
currentNode.left = new Node();
currentNode.left.key = 4;
currentNode.right = new Node();
currentNode.right.key = 8;
invalidTree.right = new Node();
invalidTree.right.key = 10;
currentNode = invalidTree.right;
currentNode.right = new Node();
currentNode.right.key = 14;
currentNode = currentNode.right;
currentNode.left = new Node();
currentNode.left.key = 13;
System.Console.WriteLine("Valid BST: " + IsValidBST(validTree));
System.Console.WriteLine("Valid BST: " + IsValidBST(invalidTree));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment