Check if given sorted sub sequence exists in binary search tree

Here given code implementation process.

/*
  Java program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinarySearchTree
{
    public TreeNode root;
    public int index;
    public BinarySearchTree()
    {
        this.root = null;
        this.index = 0;
    }
    public void addNode(int data)
    {
        // Create a new node 
        TreeNode node = new TreeNode(data);
        if (this.root == null)
        {
            // When add a first node
            this.root = node;
        }
        else
        {
            // Get root of tree
            TreeNode find = this.root;

            // Find position to insert new node
            while (find != null)
            {
                if (find.data >= data)
                {
                    if (find.left == null)
                    {
                        find.left = node;
                        return;
                    }
                    else
                    {
                        // Visit left sub-tree
                        find = find.left;
                    }
                }
                else
                {
                    if (find.right == null)
                    {
                        find.right = node;
                        return;
                    }
                    else
                    {
                        // Visit right sub-tree
                        find = find.right;
                    }
                }
            }
        }
    }
    public void findSequence(TreeNode node, int[] sequence)
    {
        if (node != null && this.index >= 0)
        {
            // Visit right subtree
            findSequence(node.right, sequence);
            if (this.index >= 0 && sequence[this.index] == node.data)
            {
                this.index = this.index - 1;
            }
            // Visit left subtree
            findSequence(node.left, sequence);
        }
    }
    public void isSortedSequenceExist(int[] sequence, int n)
    {
        if (this.root == null)
        {
            System.out.print("\n Empty Tree");
        }
        else if (n <= 0)
        {
            System.out.print("\n Empty sequence");
        }
        else
        {
            this.index = n - 1;
            System.out.print("\n Given sequence : ");
            for (int i = 0; i < n; ++i)
            {
                System.out.print(" " + sequence[i] );
            }
            findSequence(this.root, sequence);
            if (this.index >= 0)
            {
                System.out.print("\n No ");
            }
            else
            {
                System.out.print("\n Yes");
            }
        }
    }
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
        /*
                    15
                   / \ 
                  /   \ 
                 /     \
                13      20
               /  \     / \
              10  14   19  21
             / \      /      \
            5   11   17       22
                      \
                       18
            -----------------------
            Binary search tree         
        */
        // Add node
        tree.addNode(15);
        tree.addNode(13);
        tree.addNode(10);
        tree.addNode(5);
        tree.addNode(14);
        tree.addNode(11);
        tree.addNode(20);
        tree.addNode(19);
        tree.addNode(21);
        tree.addNode(22);
        tree.addNode(17);
        tree.addNode(18);
        // Sorted sequences
        int[] sequence1 =  
        {
            11 , 13 , 18 , 21
        };
        int[] sequence2 =  
        {
            10 , 12 , 17 , 21 , 22
        };
        int[] sequence3 =  
        {
            5 , 14 , 19 , 20 , 21
        };
        // Test A
        int n = sequence1.length;
        tree.isSortedSequenceExist( sequence1, n);
        // Test B
        n = sequence2.length;
        tree.isSortedSequenceExist( sequence2, n);
        // Test C
        n = sequence3.length;
        tree.isSortedSequenceExist( sequence3, n);
    }
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
/*
    C Program 
    Check if given sorted sub sequence exists in binary search tree
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Binary Search Tree
struct BinarySearchTree
{
    struct TreeNode *root;
};


// Create new tree
struct BinarySearchTree *newTree()
{
    // Create dynamic node
    struct BinarySearchTree *tree = 
      (struct BinarySearchTree *) malloc(sizeof(struct BinarySearchTree));

    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    // return new tree
    return tree;
}
// returns a new node of tree
struct TreeNode *newTreeNode(int data)
{
    // Create dynamic node
    struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        //Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        //This is indicates, segmentation fault or memory overflow problem
        printf("Memory Overflow\n");
    }
    //return new node
    return node;
}
// Adding a new node in binary search tree
void addNode(struct BinarySearchTree *tree, int data)
{
    struct TreeNode *node = newTreeNode(data);
    if (node != NULL)
    {
        if (tree->root == NULL)
        {
            tree->root = node;
        }
        else
        {
            struct TreeNode *auxiliary = tree->root;
            // Add new node in binary search tree
            while (auxiliary != NULL)
            {
                if (data > auxiliary->data)
                {
                    if (auxiliary->right == NULL)
                    {
                        // Add new node at right child
                        auxiliary->right = node;
                        return;
                    }
                    auxiliary = auxiliary->right;
                }
                else
                {
                    if (auxiliary->left == NULL)
                    {
                        // Add new node at left child
                        auxiliary->left = node;
                        return;
                    }
                    auxiliary = auxiliary->left;
                }
            }
        }
    }
}


void findSequence(struct TreeNode*node,int sequence[], int *index)
{

    if(node!=NULL && *index >= 0)
    {
        
        // Visit right subtree
        findSequence(node->right,sequence,index);
        if(*index >= 0 && sequence[*index]==node->data)
        {
            *index = *index - 1;
        }
        // Visit left subtree
        findSequence(node->left,sequence,index);
        
    }

}
void isSortedSequenceExist(struct TreeNode *root, int sequence[], int n)
{

   if(root==NULL)
   {
     printf("\n Empty Tree");
   }
   else if(n<=0)
   {
       printf("\n Empty sequence");
   }
   else
   {
      int index = n-1;

      printf("\n Given sequence : ");
      for (int i = 0; i < n ; ++i)
      {
          printf("  %d",sequence[i]);
      }

      findSequence(root,sequence,&index);


      if(index>=0)
      {
        printf("\n No ");
      }
      else
      {
        printf("\n Yes");
      }
   }
}

int main()
{   
    struct BinarySearchTree *tree = newTree();
    
    /*
                15
               / \ 
              /   \ 
             /     \
            13      20
           /  \     / \
          10  14   19  21
         / \      /      \
        5   11   17       22
                  \
                   18
        -----------------------
        Binary search tree         
    */  
    // Add node
    addNode(tree,15);
    addNode(tree,13);
    addNode(tree,10);
    addNode(tree,5);
    addNode(tree,14);
    addNode(tree,11);
    addNode(tree,20);
    addNode(tree,19);
    addNode(tree,21);
    addNode(tree,22);
    addNode(tree,17);
    addNode(tree,18);

    // Sorted sequences
    int sequence1[] = {11,13,18,21};
    int sequence2[] = {10,12,17,21,22};
    int sequence3[] = {5,14,19,20,21};

    // Test A
    int n = sizeof(sequence1) / sizeof(sequence1[0]);
    isSortedSequenceExist(tree->root,sequence1,n);

    // Test B
    n = sizeof(sequence2) / sizeof(sequence2[0]);
    isSortedSequenceExist(tree->root,sequence2,n);
    // Test C
    n = sizeof(sequence3) / sizeof(sequence3[0]);
    isSortedSequenceExist(tree->root,sequence3,n);
    return 0;
}

Output

 Given sequence :   11  13  18  21
 Yes
 Given sequence :   10  12  17  21  22
 No
 Given sequence :   5  14  19  20  21
 Yes
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: TreeNode *root;
	int index;
	BinarySearchTree()
	{
		this->root = NULL;
		this->index = 0;
	}
	void addNode(int data)
	{
		// Create a new node 
		TreeNode *node = new TreeNode(data);
		if (this->root == NULL)
		{
			// When add a first node
			this->root = node;
		}
		else
		{
			// Get root of tree
			TreeNode *find = this->root;
			// Find position to insert new node
			while (find != NULL)
			{
				if (find->data >= data)
				{
					if (find->left == NULL)
					{
						find->left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find->left;
					}
				}
				else
				{
					if (find->right == NULL)
					{
						find->right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find->right;
					}
				}
			}
		}
	}
	void findSequence(TreeNode *node, int sequence[])
	{
		if (node != NULL && this->index >= 0)
		{
			// Visit right subtree
			this->findSequence(node->right, sequence);
			if (this->index >= 0 && sequence[this->index] == node->data)
			{
				this->index = this->index - 1;
			}
			// Visit left subtree
			this->findSequence(node->left, sequence);
		}
	}
	void isSortedSequenceExist(int sequence[], int n)
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree";
		}
		else if (n <= 0)
		{
			cout << "\n Empty sequence";
		}
		else
		{
			this->index = n - 1;
			cout << "\n Given sequence : ";
			for (int i = 0; i < n; ++i)
			{
				cout << " " << sequence[i];
			}
			this->findSequence(this->root, sequence);
			if (this->index >= 0)
			{
				cout << "\n No ";
			}
			else
			{
				cout << "\n Yes";
			}
		}
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	tree->addNode(15);
	tree->addNode(13);
	tree->addNode(10);
	tree->addNode(5);
	tree->addNode(14);
	tree->addNode(11);
	tree->addNode(20);
	tree->addNode(19);
	tree->addNode(21);
	tree->addNode(22);
	tree->addNode(17);
	tree->addNode(18);
	// Sorted sequences
	int sequence1[] = {
		11 , 13 , 18 , 21
	};
	int sequence2[] = {
		10 , 12 , 17 , 21 , 22
	};
	int sequence3[] = {
		5 , 14 , 19 , 20 , 21
	};
	// Test A
	int n = sizeof(sequence1) / sizeof(sequence1[0]);
	tree->isSortedSequenceExist(sequence1, n);
	// Test B
	n = sizeof(sequence2) / sizeof(sequence2[0]);
	tree->isSortedSequenceExist(sequence2, n);
	// Test C
	n = sizeof(sequence3) / sizeof(sequence3[0]);
	tree->isSortedSequenceExist(sequence3, n);
	return 0;
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
package main
import "fmt"
/*
  Go program
  Check if given sorted sub sequence exists in binary search tree
*/
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.data = data
	me.left = nil
	me.right = nil
	return me
}
type BinarySearchTree struct {
	root * TreeNode
	index int
}
func getBinarySearchTree() * BinarySearchTree {
	var me *BinarySearchTree = &BinarySearchTree {}
	me.root = nil
	me.index = 0
	return me
}
func(this *BinarySearchTree) addNode(data int) {
	// Create a new node 
	var node * TreeNode = getTreeNode(data)
	if this.root == nil {
		// When add a first node
		this.root = node
	} else {
		// Get root of tree
		var find * TreeNode = this.root
		// Find position to insert new node
		for (find != nil) {
			if find.data >= data {
				if find.left == nil {
					find.left = node
					return
				} else {
					// Visit left sub-tree
					find = find.left
				}
			} else {
				if find.right == nil {
					find.right = node
					return
				} else {
					// Visit right sub-tree
					find = find.right
				}
			}
		}
	}
}
func(this *BinarySearchTree) findSequence(node * TreeNode, 
	sequence[] int) {
	if node != nil && this.index >= 0 {
		// Visit right subtree
		this.findSequence(node.right, sequence)
		if this.index >= 0 && sequence[this.index] == node.data {
			this.index = this.index - 1
		}
		// Visit left subtree
		this.findSequence(node.left, sequence)
	}
}
func(this *BinarySearchTree) isSortedSequenceExist(sequence[] int, 
	n int) {
	if this.root == nil {
		fmt.Print("\n Empty Tree")
	} else if n <= 0 {
		fmt.Print("\n Empty sequence")
	} else {
		this.index = n - 1
		fmt.Print("\n Given sequence : ")
		for i := 0 ; i < n ; i++ {
			fmt.Print(" ", sequence[i])
		}
		this.findSequence(this.root, sequence)
		if this.index >= 0 {
			fmt.Print("\n No ")
		} else {
			fmt.Print("\n Yes")
		}
	}
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	tree.addNode(15)
	tree.addNode(13)
	tree.addNode(10)
	tree.addNode(5)
	tree.addNode(14)
	tree.addNode(11)
	tree.addNode(20)
	tree.addNode(19)
	tree.addNode(21)
	tree.addNode(22)
	tree.addNode(17)
	tree.addNode(18)
	// Sorted sequences
	var sequence1 = [] int {
		11,
		13,
		18,
		21,
	}
	var sequence2 = [] int {
		10,
		12,
		17,
		21,
		22,
	}
	var sequence3 = [] int {
		5,
		14,
		19,
		20,
		21,
	}
	// Test A
	var n int = len(sequence1)
	tree.isSortedSequenceExist(sequence1, n)
	// Test B
	n = len(sequence2)
	tree.isSortedSequenceExist(sequence2, n)
	// Test C
	n = len(sequence3)
	tree.isSortedSequenceExist(sequence3, n)
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
// Include namespace system
using System;
/*
  Csharp program
  Check if given sorted sub sequence exists in binary search tree
*/
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public int index;
	public BinarySearchTree()
	{
		this.root = null;
		this.index = 0;
	}
	public void addNode(int data)
	{
		// Create a new node 
		TreeNode node = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			TreeNode find = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	public void findSequence(TreeNode node, int[] sequence)
	{
		if (node != null && this.index >= 0)
		{
			// Visit right subtree
			this.findSequence(node.right, sequence);
			if (this.index >= 0 && sequence[this.index] == node.data)
			{
				this.index = this.index - 1;
			}
			// Visit left subtree
			this.findSequence(node.left, sequence);
		}
	}
	public void isSortedSequenceExist(int[] sequence, int n)
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree");
		}
		else if (n <= 0)
		{
			Console.Write("\n Empty sequence");
		}
		else
		{
			this.index = n - 1;
			Console.Write("\n Given sequence : ");
			for (int i = 0; i < n; ++i)
			{
				Console.Write(" " + sequence[i]);
			}
			this.findSequence(this.root, sequence);
			if (this.index >= 0)
			{
				Console.Write("\n No ");
			}
			else
			{
				Console.Write("\n Yes");
			}
		}
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		/*
		            15
		           / \ 
		          /   \ 
		         /     \
		        13      20
		       /  \     / \
		      10  14   19  21
		     / \      /      \
		    5   11   17       22
		              \
		               18
		    -----------------------
		    Binary search tree         
		*/
		// Add node
		tree.addNode(15);
		tree.addNode(13);
		tree.addNode(10);
		tree.addNode(5);
		tree.addNode(14);
		tree.addNode(11);
		tree.addNode(20);
		tree.addNode(19);
		tree.addNode(21);
		tree.addNode(22);
		tree.addNode(17);
		tree.addNode(18);
		// Sorted sequences
		int[] sequence1 = {
			11 , 13 , 18 , 21
		};
		int[] sequence2 = {
			10 , 12 , 17 , 21 , 22
		};
		int[] sequence3 = {
			5 , 14 , 19 , 20 , 21
		};
		// Test A
		int n = sequence1.Length;
		tree.isSortedSequenceExist(sequence1, n);
		// Test B
		n = sequence2.Length;
		tree.isSortedSequenceExist(sequence2, n);
		// Test C
		n = sequence3.Length;
		tree.isSortedSequenceExist(sequence3, n);
	}
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
<?php
/*
  Php program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public $index;
	public	function __construct()
	{
		$this->root = NULL;
		$this->index = 0;
	}
	public	function addNode($data)
	{
		// Create a new node 
		$node = new TreeNode($data);
		if ($this->root == NULL)
		{
			// When add a first node
			$this->root = $node;
		}
		else
		{
			// Get root of tree
			$find = $this->root;
			// Find position to insert new node
			while ($find != NULL)
			{
				if ($find->data >= $data)
				{
					if ($find->left == NULL)
					{
						$find->left = $node;
						return;
					}
					else
					{
						// Visit left sub-tree
						$find = $find->left;
					}
				}
				else
				{
					if ($find->right == NULL)
					{
						$find->right = $node;
						return;
					}
					else
					{
						// Visit right sub-tree
						$find = $find->right;
					}
				}
			}
		}
	}
	public	function findSequence($node, $sequence)
	{
		if ($node != NULL && $this->index >= 0)
		{
			// Visit right subtree
			$this->findSequence($node->right, $sequence);
			if ($this->index >= 0 && $sequence[$this->index] == $node->data)
			{
				$this->index = $this->index - 1;
			}
			// Visit left subtree
			$this->findSequence($node->left, $sequence);
		}
	}
	public	function isSortedSequenceExist($sequence, $n)
	{
		if ($this->root == NULL)
		{
			echo("\n Empty Tree");
		}
		else if ($n <= 0)
		{
			echo("\n Empty sequence");
		}
		else
		{
			$this->index = $n - 1;
			echo("\n Given sequence : ");
			for ($i = 0; $i < $n; ++$i)
			{
				echo(" ".$sequence[$i]);
			}
			$this->findSequence($this->root, $sequence);
			if ($this->index >= 0)
			{
				echo("\n No ");
			}
			else
			{
				echo("\n Yes");
			}
		}
	}
}

function main()
{
	$tree = new BinarySearchTree();
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	$tree->addNode(15);
	$tree->addNode(13);
	$tree->addNode(10);
	$tree->addNode(5);
	$tree->addNode(14);
	$tree->addNode(11);
	$tree->addNode(20);
	$tree->addNode(19);
	$tree->addNode(21);
	$tree->addNode(22);
	$tree->addNode(17);
	$tree->addNode(18);
	// Sorted sequences
	$sequence1 = array(11, 13, 18, 21);
	$sequence2 = array(10, 12, 17, 21, 22);
	$sequence3 = array(5, 14, 19, 20, 21);
	// Test A
	$n = count($sequence1);
	$tree->isSortedSequenceExist($sequence1, $n);
	// Test B
	$n = count($sequence2);
	$tree->isSortedSequenceExist($sequence2, $n);
	// Test C
	$n = count($sequence3);
	$tree->isSortedSequenceExist($sequence3, $n);
}
main();

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
/*
  Node JS program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
		this.index = 0;
	}
	addNode(data)
	{
		// Create a new node 
		var node = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	findSequence(node, sequence)
	{
		if (node != null && this.index >= 0)
		{
			// Visit right subtree
			this.findSequence(node.right, sequence);
			if (this.index >= 0 && sequence[this.index] == node.data)
			{
				this.index = this.index - 1;
			}
			// Visit left subtree
			this.findSequence(node.left, sequence);
		}
	}
	isSortedSequenceExist(sequence, n)
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree");
		}
		else if (n <= 0)
		{
			process.stdout.write("\n Empty sequence");
		}
		else
		{
			this.index = n - 1;
			process.stdout.write("\n Given sequence : ");
			for (var i = 0; i < n; ++i)
			{
				process.stdout.write(" " + sequence[i]);
			}
			this.findSequence(this.root, sequence);
			if (this.index >= 0)
			{
				process.stdout.write("\n No ");
			}
			else
			{
				process.stdout.write("\n Yes");
			}
		}
	}
}

function main()
{
	var tree = new BinarySearchTree();
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	tree.addNode(15);
	tree.addNode(13);
	tree.addNode(10);
	tree.addNode(5);
	tree.addNode(14);
	tree.addNode(11);
	tree.addNode(20);
	tree.addNode(19);
	tree.addNode(21);
	tree.addNode(22);
	tree.addNode(17);
	tree.addNode(18);
	// Sorted sequences
	var sequence1 = [11, 13, 18, 21];
	var sequence2 = [10, 12, 17, 21, 22];
	var sequence3 = [5, 14, 19, 20, 21];
	// Test A
	var n = sequence1.length;
	tree.isSortedSequenceExist(sequence1, n);
	// Test B
	n = sequence2.length;
	tree.isSortedSequenceExist(sequence2, n);
	// Test C
	n = sequence3.length;
	tree.isSortedSequenceExist(sequence3, n);
}
main();

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
#  Python 3 program
#  Check if given sorted sub sequence exists in binary search tree
class TreeNode :
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
		self.index = 0
	
	def addNode(self, data) :
		#  Create a new node 
		node = TreeNode(data)
		if (self.root == None) :
			#  When add a first node
			self.root = node
		else :
			#  Get root of tree
			find = self.root
			#  Find position to insert new node
			while (find != None) :
				if (find.data >= data) :
					if (find.left == None) :
						find.left = node
						return
					else :
						#  Visit left sub-tree
						find = find.left
					
				else :
					if (find.right == None) :
						find.right = node
						return
					else :
						#  Visit right sub-tree
						find = find.right
					
				
			
		
	
	def findSequence(self, node, sequence) :
		if (node != None and self.index >= 0) :
			#  Visit right subtree
			self.findSequence(node.right, sequence)
			if (self.index >= 0 and sequence[self.index] == node.data) :
				self.index = self.index - 1
			
			#  Visit left subtree
			self.findSequence(node.left, sequence)
		
	
	def isSortedSequenceExist(self, sequence, n) :
		if (self.root == None) :
			print("\n Empty Tree", end = "")
		elif (n <= 0) :
			print("\n Empty sequence", end = "")
		else :
			self.index = n - 1
			print("\n Given sequence : ", end = "")
			i = 0
			while (i < n) :
				print(" ", sequence[i], end = "")
				i += 1
			
			self.findSequence(self.root, sequence)
			if (self.index >= 0) :
				print("\n No ", end = "")
			else :
				print("\n Yes", end = "")
			
		
	

def main() :
	tree = BinarySearchTree()
	#            15
	#           / \ 
	#          /   \ 
	#         /     \
	#        13      20
	#       /  \     / \
	#      10  14   19  21
	#     / \      /      \
	#    5   11   17       22
	#              \
	#               18
	#    -----------------------
	#    Binary search tree         
	#  Add node
	tree.addNode(15)
	tree.addNode(13)
	tree.addNode(10)
	tree.addNode(5)
	tree.addNode(14)
	tree.addNode(11)
	tree.addNode(20)
	tree.addNode(19)
	tree.addNode(21)
	tree.addNode(22)
	tree.addNode(17)
	tree.addNode(18)
	#  Sorted sequences
	sequence1 = [11, 13, 18, 21]
	sequence2 = [10, 12, 17, 21, 22]
	sequence3 = [5, 14, 19, 20, 21]
	#  Test A
	n = len(sequence1)
	tree.isSortedSequenceExist(sequence1, n)
	#  Test B
	n = len(sequence2)
	tree.isSortedSequenceExist(sequence2, n)
	#  Test C
	n = len(sequence3)
	tree.isSortedSequenceExist(sequence3, n)

if __name__ == "__main__": main()

Output

 Given sequence :   11  13  18  21
 Yes
 Given sequence :   10  12  17  21  22
 No
 Given sequence :   5  14  19  20  21
 Yes
#  Ruby program
#  Check if given sorted sub sequence exists in binary search tree
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinarySearchTree 
	# Define the accessor and reader of class Binary Search Tree
	attr_reader :root, :index
	attr_accessor :root, :index
	def initialize() 
		self.root = nil
		self.index = 0
	end

	def addNode(data) 
		#  Create a new node 
		node = TreeNode.new(data)
		if (self.root == nil) 
			#  When add a first node
			self.root = node
		else
 
			#  Get root of tree
			find = self.root
			#  Find position to insert new node
			while (find != nil) 
				if (find.data >= data) 
					if (find.left == nil) 
						find.left = node
						return
					else
 
						#  Visit left sub-tree
						find = find.left
					end

				else
 
					if (find.right == nil) 
						find.right = node
						return
					else
 
						#  Visit right sub-tree
						find = find.right
					end

				end

			end

		end

	end

	def findSequence(node, sequence) 
		if (node != nil && self.index >= 0) 
			#  Visit right subtree
			self.findSequence(node.right, sequence)
			if (self.index >= 0 && sequence[self.index] == node.data) 
				self.index = self.index - 1
			end

			#  Visit left subtree
			self.findSequence(node.left, sequence)
		end

	end

	def isSortedSequenceExist(sequence, n) 
		if (self.root == nil) 
			print("\n Empty Tree")
		elsif (n <= 0) 
			print("\n Empty sequence")
		else
 
			self.index = n - 1
			print("\n Given sequence : ")
			i = 0
			while (i < n) 
				print(" ", sequence[i])
				i += 1
			end

			self.findSequence(self.root, sequence)
			if (self.index >= 0) 
				print("\n No ")
			else
 
				print("\n Yes")
			end

		end

	end

end

def main() 
	tree = BinarySearchTree.new()
	#            15
	#           / \ 
	#          /   \ 
	#         /     \
	#        13      20
	#       /  \     / \
	#      10  14   19  21
	#     / \      /      \
	#    5   11   17       22
	#              \
	#               18
	#    -----------------------
	#    Binary search tree         
	#  Add node
	tree.addNode(15)
	tree.addNode(13)
	tree.addNode(10)
	tree.addNode(5)
	tree.addNode(14)
	tree.addNode(11)
	tree.addNode(20)
	tree.addNode(19)
	tree.addNode(21)
	tree.addNode(22)
	tree.addNode(17)
	tree.addNode(18)
	#  Sorted sequences
	sequence1 = [11, 13, 18, 21]
	sequence2 = [10, 12, 17, 21, 22]
	sequence3 = [5, 14, 19, 20, 21]
	#  Test A
	n = sequence1.length
	tree.isSortedSequenceExist(sequence1, n)
	#  Test B
	n = sequence2.length
	tree.isSortedSequenceExist(sequence2, n)
	#  Test C
	n = sequence3.length
	tree.isSortedSequenceExist(sequence3, n)
end

main()

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No 
 Given sequence :  5 14 19 20 21
 Yes
/*
  Scala program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinarySearchTree(var root: TreeNode,
	var index: Int)
{
	def this()
	{
		this(null, 0);
	}
	def addNode(data: Int): Unit = {
		// Create a new node 
		var node: TreeNode = new TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	def findSequence(node: TreeNode, sequence: Array[Int]): Unit = {
		if (node != null && this.index >= 0)
		{
			// Visit right subtree
			findSequence(node.right, sequence);
			if (this.index >= 0 && sequence(this.index) == node.data)
			{
				this.index = this.index - 1;
			}
			// Visit left subtree
			findSequence(node.left, sequence);
		}
	}
	def isSortedSequenceExist(sequence: Array[Int], n: Int): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree");
		}
		else if (n <= 0)
		{
			print("\n Empty sequence");
		}
		else
		{
			this.index = n - 1;
			print("\n Given sequence : ");
			var i: Int = 0;
			while (i < n)
			{
				print(" " + sequence(i));
				i += 1;
			}
			findSequence(this.root, sequence);
			if (this.index >= 0)
			{
				print("\n No ");
			}
			else
			{
				print("\n Yes");
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		/*
		            15
		           / \ 
		          /   \ 
		         /     \
		        13      20
		       /  \     / \
		      10  14   19  21
		     / \      /      \
		    5   11   17       22
		              \
		               18
		    -----------------------
		    Binary search tree         
		*/
		// Add node
		tree.addNode(15);
		tree.addNode(13);
		tree.addNode(10);
		tree.addNode(5);
		tree.addNode(14);
		tree.addNode(11);
		tree.addNode(20);
		tree.addNode(19);
		tree.addNode(21);
		tree.addNode(22);
		tree.addNode(17);
		tree.addNode(18);
		// Sorted sequences
		var sequence1: Array[Int] = Array(11, 13, 18, 21);
		var sequence2: Array[Int] = Array(10, 12, 17, 21, 22);
		var sequence3: Array[Int] = Array(5, 14, 19, 20, 21);
		// Test A
		var n: Int = sequence1.length;
		tree.isSortedSequenceExist(sequence1, n);
		// Test B
		n = sequence2.length;
		tree.isSortedSequenceExist(sequence2, n);
		// Test C
		n = sequence3.length;
		tree.isSortedSequenceExist(sequence3, n);
	}
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes
import Foundation;
/*
  Swift 4 program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	var index: Int;
	init()
	{
		self.root = nil;
		self.index = 0;
	}
	func addNode(_ data: Int)
	{
		// Create a new node 
		let node: TreeNode = TreeNode(data);
		if (self.root == nil)
		{
			// When add a first node
			self.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode? = self.root;
			// Find position to insert new node
			while (find  != nil)
			{
				if (find!.data >= data)
				{
					if (find!.left == nil)
					{
						find!.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find!.left;
					}
				}
				else
				{
					if (find!.right == nil)
					{
						find!.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find!.right;
					}
				}
			}
		}
	}
	func findSequence(_ node: TreeNode? , _ sequence : [Int])
	{
		if (node  != nil && self.index >= 0)
		{
			// Visit right subtree
			self.findSequence(node!.right, sequence);
			if (self.index >= 0 && sequence[self.index] == node!.data)
			{
				self.index = self.index - 1;
			}
			// Visit left subtree
			self.findSequence(node!.left, sequence);
		}
	}
	func isSortedSequenceExist(_ sequence: [Int], _ n: Int)
	{
		if (self.root == nil)
		{
			print("\n Empty Tree", terminator: "");
		}
		else if (n <= 0)
		{
			print("\n Empty sequence", terminator: "");
		}
		else
		{
			self.index = n - 1;
			print("\n Given sequence : ", terminator: "");
			var i: Int = 0;
			while (i < n)
			{
				print(" ", sequence[i], terminator: "");
				i += 1;
			}
			self.findSequence(self.root, sequence);
			if (self.index >= 0)
			{
				print("\n No ", terminator: "");
			}
			else
			{
				print("\n Yes", terminator: "");
			}
		}
	}
}
func main()
{
	let tree: BinarySearchTree = BinarySearchTree();
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	tree.addNode(15);
	tree.addNode(13);
	tree.addNode(10);
	tree.addNode(5);
	tree.addNode(14);
	tree.addNode(11);
	tree.addNode(20);
	tree.addNode(19);
	tree.addNode(21);
	tree.addNode(22);
	tree.addNode(17);
	tree.addNode(18);
	// Sorted sequences
	let sequence1: [Int] = [11, 13, 18, 21];
	let sequence2: [Int] = [10, 12, 17, 21, 22];
	let sequence3: [Int] = [5, 14, 19, 20, 21];
	// Test A
	var n: Int = sequence1.count;
	tree.isSortedSequenceExist(sequence1, n);
	// Test B
	n = sequence2.count;
	tree.isSortedSequenceExist(sequence2, n);
	// Test C
	n = sequence3.count;
	tree.isSortedSequenceExist(sequence3, n);
}
main();

Output

 Given sequence :   11  13  18  21
 Yes
 Given sequence :   10  12  17  21  22
 No
 Given sequence :   5  14  19  20  21
 Yes
/*
  Kotlin program
  Check if given sorted sub sequence exists in binary search tree
*/
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	var index: Int;
	constructor()
	{
		this.root = null;
		this.index = 0;
	}
	fun addNode(data: Int): Unit
	{
		// Create a new node 
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			// When add a first node
			this.root = node;
		}
		else
		{
			// Get root of tree
			var find: TreeNode ? = this.root;
			// Find position to insert new node
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						find.left = node;
						return;
					}
					else
					{
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	fun findSequence(node: TreeNode ? , sequence : Array < Int > ): Unit
	{
		if (node != null && this.index >= 0)
		{
			// Visit right subtree
			this.findSequence(node.right, sequence);
			if (this.index >= 0 && sequence[this.index] == node.data)
			{
				this.index = this.index - 1;
			}
			// Visit left subtree
			this.findSequence(node.left, sequence);
		}
	}
	fun isSortedSequenceExist(sequence: Array < Int > , n: Int): Unit
	{
		if (this.root == null)
		{
			print("\n Empty Tree");
		}
		else if (n <= 0)
		{
			print("\n Empty sequence");
		}
		else
		{
			this.index = n - 1;
			print("\n Given sequence : ");
			var i: Int = 0;
			while (i < n)
			{
				print(" " + sequence[i]);
				i += 1;
			}
			this.findSequence(this.root, sequence);
			if (this.index >= 0)
			{
				print("\n No ");
			}
			else
			{
				print("\n Yes");
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	/*
	            15
	           / \ 
	          /   \ 
	         /     \
	        13      20
	       /  \     / \
	      10  14   19  21
	     / \      /      \
	    5   11   17       22
	              \
	               18
	    -----------------------
	    Binary search tree         
	*/
	// Add node
	tree.addNode(15);
	tree.addNode(13);
	tree.addNode(10);
	tree.addNode(5);
	tree.addNode(14);
	tree.addNode(11);
	tree.addNode(20);
	tree.addNode(19);
	tree.addNode(21);
	tree.addNode(22);
	tree.addNode(17);
	tree.addNode(18);
	// Sorted sequences
	val sequence1: Array < Int > = arrayOf(11, 13, 18, 21);
	val sequence2: Array < Int > = arrayOf(10, 12, 17, 21, 22);
	val sequence3: Array < Int > = arrayOf(5, 14, 19, 20, 21);
	// Test A
	var n: Int = sequence1.count();
	tree.isSortedSequenceExist(sequence1, n);
	// Test B
	n = sequence2.count();
	tree.isSortedSequenceExist(sequence2, n);
	// Test C
	n = sequence3.count();
	tree.isSortedSequenceExist(sequence3, n);
}

Output

 Given sequence :  11 13 18 21
 Yes
 Given sequence :  10 12 17 21 22
 No
 Given sequence :  5 14 19 20 21
 Yes


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved