Check if a binary tree is subtree of another binary tree

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        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;
            }
        }

        static void Main(string[] args)
        {
            //    0           1
            //   / \         / \ 
            //  1   2       3   4
            // / \
            //3   4

            //Initializing the tree structure
            Node three = new Node(null, null, 3);
            Node four = new Node(null, null, 4);
            Node one = new Node(three, four, 1);
            Node two = new Node(null, null, 2);
            Node root = new Node(one, two, 0);
            //Subtree
            Node three1 = new Node(null, null, 3);
            Node four1 = new Node(null, null, 4);
            Node root1 = new Node(three1, four1, 1);
            //Check
            Console.WriteLine(CheckSubTree(root, root1));
        }
        public static bool CheckSubTree(Node root, Node root1)
        {
            if (root1 == null)
                return true;
            else if (root == null)
                return false;
            else
            {
                //Non Recursive Pre-Order Traversal
                Stack nodeStack = new Stack();
                nodeStack.Push(root);
                while (nodeStack.Count != 0)
                {
                    Node tempNode = (Node)nodeStack.Pop();
                    if (tempNode.getValue() == root1.getValue())
                    {
                        if (IsSubTree(tempNode, root1))
                            return true;
                    }
                    if (tempNode.getRight() != null)
                        nodeStack.Push(tempNode.getRight());
                    if (tempNode.getLeft() != null)
                        nodeStack.Push(tempNode.getLeft());
                }
            }
            return false;
        }

        public static bool IsSubTree(Node root, Node root1)
        {
            if (root1 == null)
                return true;
            else if (root == null)
                return false;
            else if (root.getValue() == root1.getValue())
                return (IsSubTree(root.getLeft(), root1.getLeft()) && IsSubTree(root.getRight(), root1.getRight()));
            else
                return false;
        }
    }
}

Output
======
True
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