Write a function that returns whether a given binary tree is a valid binary search tree.

CodingInterviewPractice_2012_12_17.cs

/****************************************************************
    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));
        }
    }
}