Validating a binary search tree

Do an in-order traversal of the tree and store the node values in an array. If the array is in sorted order, it’s a valid BST otherwise not.

 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

    public class Node

    {

        private Node left;

        private Node right;

        private int value;

        public Node(Node left, Node right, int value)

        {

            this.left = left;

            this.right = right;

            this.value = value;

        }

        public Node getLeft()

        {

            return left;

        }

        public Node getRight()

        {

            return right;

        }

        public int getValue()

        {

            return value;

        }

    }

 

    class Program

    {

        static void Main(string[] args)

        {

            //Initializing the tree structure

            Node bottomFirst = new Node(null, null, 1);

            Node bottomSecond = new Node(null, null, 4);

            Node bottomThird = new Node(null, null, 7);

            Node bottomFourth = new Node(null, null, 12);

            Node middleFirst = new Node(bottomFirst, bottomSecond, 3);

            Node middleSecond = new Node(bottomThird, bottomFourth, 10);

            Node root = new Node(middleFirst, middleSecond, 5);

            List<int> numList = new List<int>();

            Console.WriteLine("InOrderTraversal");

            Console.WriteLine("================");

            InOrderTraversal(root, numList);

            for (int i = 0; i < numList.Count; i++)

            {

                Console.Write(numList[i] + " ");

            }

            Console.WriteLine();

            if (IsSorted(numList))

            {

                Console.WriteLine("========================");

                Console.WriteLine("It’s a valid binary tree");

                Console.WriteLine("========================");

            }

            else

            {

                Console.WriteLine("===========================");

                Console.WriteLine("It’s an invalid binary tree");

                Console.WriteLine("===========================");

            }

        }

        public static void InOrderTraversal(Node root, List<int> numList)

        {

            if (root == null)

            {

                return;

            }

            InOrderTraversal(root.getLeft(), numList);

            numList.Add(root.getValue());

            InOrderTraversal(root.getRight(), numList);

        }

        public static bool IsSorted(List<int> numList)

        {

            for (int i = 0; i < numList.Count – 1; i++)

            {

                if (numList[i] > numList[i + 1])

                {

                    return false;

                }

            }

            return true;

        }

    }

}

 

InOrderTraversal
================
1 3 4 5 7 10 12
========================
It’s a valid binary tree
========================
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s