Skip to main content

Check if two BST contain same set of elements

Check if two BSTS contain same set of elements

Here given code implementation process.

//C Program 
//Check if two BST contain same set of elements
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}
int  count_element(struct Node*root)
{
  if(root!=NULL)
  {
   return count_element(root->left)+count_element(root->right)+1;
  }
  return 0;
 
}
void get_element(struct Node*root,int *index,int *auxiliary)
{
  if(root!=NULL)
  {
    get_element(root->left,index,auxiliary);
    
    auxiliary[*index]=root->data;
    (*index)++;
    get_element(root->right,index,auxiliary);
  }

}
void compare_element(struct Node*root,int *index,int *auxiliary)
{
 
  if(root!=NULL)
  {
    compare_element(root->left,index,auxiliary);
    
    if(root->data==auxiliary[*index])
    {
      (*index)++;
    }
    compare_element(root->right,index,auxiliary);
  }

 
}
void same_set(struct Node*root1,struct Node*root2)
{
  if(root1 != NULL && root2)
  {
   int size=count_element(root1);

   if(size==count_element(root2))
   {
     int *auxiliary=(int*)malloc(sizeof(int)*size);
     int index=0;
     get_element(root1,&index,auxiliary);
     index=0;
     compare_element(root2,&index,auxiliary);
     if(index<size)
     {
      //When node element value are not similar
      printf("\n Not\n");
     }
     else
     {
      printf("\n Yes\n");
     }

     free(auxiliary);
     auxiliary=NULL;

   }
   else
   {
    //When length of nodes are not same in Tree
    printf("\n Not\n");
   }
  }
  else
  {
    printf("\n Empty Tree\n");
    
  }
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){
    
  struct Node*root1 = NULL,*root2=NULL;

  //Add nodes in binary search tree
  /*
          6
        /    \
       /      \
      3        9
     /  \      / 
    1    5    7   

    inorder = 1,3,5,6,7,9
  */                


    add(&root1,6); 
    add(&root1,3); 
    add(&root1,9); 
    add(&root1,1); 
    add(&root1,5); 
    add(&root1,7); 

  /*
        3
      /   \
     1     7
          /  \ 
         5    9
          \
           6  
    inorder = 1,3,5,6,7,9
  */       
    add(&root2,3); 
    add(&root2,1); 
    add(&root2,7); 
    add(&root2,5); 
    add(&root2,9); 
    add(&root2,6); 



    printf("First Tree inorder  \n");
    inorder(root1);

    printf("\nSecond Tree inorder \n");
    inorder(root2);
    
    same_set(root1,root2);
  return 0;
}

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
/*
 C++ Program
 Check if two BST contain same set of elements
*/

#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  int counter;
  BinarySearchTree() {
    this->root = NULL;
    this->counter = 0;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "\nMemory Overflow\n";
    }
  }
  int counter_nodes(Node *head) {
    if (head != NULL) {
      return this->counter_nodes(head->left) + this->counter_nodes(head->right) + 1;
    }
    return 0;
  }
  void get_elements(Node *head, int auxiliary[]) {
    if (head != NULL) {
      this->get_elements(head->left, auxiliary);
      auxiliary[this->counter] += head->data;
      this->counter++;
      this->get_elements(head->right, auxiliary);
    }
  }
  void compare_element(Node *head, int auxiliary[]) {
    if (head != NULL) {
      this->compare_element(head->left, auxiliary);
      if (head->data == auxiliary[this->counter]) {
        this->counter++;
      }
      this->compare_element(head->right, auxiliary);
    }
  }
  void same_set(Node *root1, Node *root2) {
    if (root1 == NULL && root2 != NULL && root2 == NULL && root1 != NULL) {
      cout<< "\nNo\n";
    } else {
      int size = this->counter_nodes(root1);
      if (size != this->counter_nodes(root2)) {
        cout << "\nNo\n";
        return;
      }
      int *auxiliary = new int[size];
      
      this->counter = 0;
      this->get_elements(root1, auxiliary);
      this->counter = 0;
      this->compare_element(root2, auxiliary);
      if (this->counter != size) {
        cout << "\nNo\n";
      } else {
        cout << "\nYes\n";
      }
    }
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << head->data << "  ";
      this->inorder(head->right);
    }
  }
};

int main() {
  BinarySearchTree obj1;
  BinarySearchTree obj2;
 /*
          6
        /    \
       /      \
      3        9
     /  \      / 
    1    5    7   

    inorder = 1,3,5,6,7,9
  */        
  obj1.add(6);
  obj1.add(3);
  obj1.add(9);
  obj1.add(1);
  obj1.add(5);
  obj1.add(7);

  /*
        3
      /   \
     1     7
          /  \ 
         5    9
          \
           6  
    inorder = 1,3,5,6,7,9
  */       
  obj2.add(3);
  obj2.add(1);
  obj2.add(7);
  obj2.add(5);
  obj2.add(9);
  obj2.add(6);
  cout << "First Tree inorder  \n";
  obj1.inorder(obj1.root);
  cout << "\nSecond Tree inorder  \n";
  obj2.inorder(obj2.root);
  obj1.same_set(obj1.root, obj2.root);

  return 0;
}

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
//Java program
//Check if two BST contain same set of elements

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;

  public int counter;


  BinarySearchTree() {
    root = null;
    counter = 0;
  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != null) {
      if (root == null) {
        //When adds a first node in binary tree
        root = new_node;
      } else {
        Node find = root;

        //add new node to proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      System.out.print("\nMemory Overflow\n");
    }
  }
  public int counter_nodes(Node head) {
    if (head != null) {

      return counter_nodes(head.left) + counter_nodes(head.right) + 1;

    }
    return 0;
  }
  public void get_elements(Node head, int[] auxiliary) {
    if (head != null) {


      get_elements(head.left, auxiliary);
      auxiliary[this.counter] += head.data;
      this.counter++;
      get_elements(head.right, auxiliary);


    }
  }
  public void compare_element(Node head, int[] auxiliary) {

    if (head != null) {
      compare_element(head.left, auxiliary);

      if (head.data == auxiliary[this.counter]) {
        this.counter++;
      }
      compare_element(head.right, auxiliary);
    }


  }
  public void same_set(Node root1, Node root2) {
    if (root1 == null && root2 != null && root2 == null && root1 != null) {
        System.out.print("\nNo\n");
    } else {

      int size = counter_nodes(root1);

      if (size != counter_nodes(root2)) {
        //not same set of elements
        System.out.print("\nNo\n");
        return;
      }

      int[] auxiliary = new int[size];

      this.counter = 0;

      get_elements(root1, auxiliary);

      this.counter = 0;

      compare_element(root2, auxiliary);

      if (this.counter != size) {
        System.out.print("\nNo\n");
      } else {
        System.out.print("\nYes\n");
      }
    }

  }
  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      System.out.print(head.data + "  ");
      inorder(head.right);
    }
  }
  public static void main(String[] args) {

    BinarySearchTree obj1 = new BinarySearchTree();
    BinarySearchTree obj2 = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
            6
          /    \
         /      \
        3        9
       /  \      / 
      1    5    7   

      inorder = 1,3,5,6,7,9
    */


    obj1.add(6);
    obj1.add(3);
    obj1.add(9);
    obj1.add(1);
    obj1.add(5);
    obj1.add(7);

    /*
          3
        /   \
       1     7
            /  \ 
           5    9
            \
             6  
      inorder = 1,3,5,6,7,9
    */
    obj2.add(3);
    obj2.add(1);
    obj2.add(7);
    obj2.add(5);
    obj2.add(9);
    obj2.add(6);

    System.out.print("First Tree inorder  \n");
    obj1.inorder(obj1.root);

    System.out.print("\nSecond Tree inorder   \n");
    obj2.inorder(obj2.root);

    obj1.same_set(obj1.root, obj2.root);
  }
}

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
//C# program
//Check if two BST contain same set of elements
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;

	public int counter;


	BinarySearchTree() {
		root = null;
		counter = 0;
	}
	//insert a node in BST
	public void add(int value) {
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if (new_node != null) {
			if (root == null) {
				//When adds a first node in binary tree
				root = new_node;
			} else {
				Node find = root;

				//add new node to proper position
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							//visit left sub-tree
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		} else {
			Console.Write("\nMemory Overflow\n");
		}
	}
	public int counter_nodes(Node head) {
		if (head != null) {

			return counter_nodes(head.left) + counter_nodes(head.right) + 1;

		}
		return 0;
	}
	public void get_elements(Node head, int[] auxiliary) {
		if (head != null) {


			get_elements(head.left, auxiliary);
			auxiliary[this.counter] += head.data;
			this.counter++;
			get_elements(head.right, auxiliary);


		}
	}
	public void compare_element(Node head, int[] auxiliary) {

		if (head != null) {
			compare_element(head.left, auxiliary);

			if (head.data == auxiliary[this.counter]) {
				this.counter++;
			}
			compare_element(head.right, auxiliary);
		}


	}
	public void same_set(Node root1, Node root2) {
		if (root1 == null && root2 != null && root2 == null && root1 != null) {
			Console.Write("\nNo\n");
		} else {

			int size = counter_nodes(root1);

			if (size != counter_nodes(root2)) {
				//not same set of elements
				Console.Write("\nNo\n");
				return;
			}

			int[] auxiliary = new int[size];

			this.counter = 0;

			get_elements(root1, auxiliary);

			this.counter = 0;

			compare_element(root2, auxiliary);

			if (this.counter != size) {
				Console.Write("\nNo\n");
			} else {
				Console.Write("\nYes\n");
			}
		}

	}
	public void inorder(Node head) {
		if (head != null) {

			inorder(head.left);
			Console.Write(head.data + "  ");
			inorder(head.right);
		}
	}
	public static void Main(String[] args) {

		BinarySearchTree obj1 = new BinarySearchTree();
		BinarySearchTree obj2 = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
            6
          /    \
         /      \
        3        9
       /  \      / 
      1    5    7   

      inorder = 1,3,5,6,7,9
    */


		obj1.add(6);
		obj1.add(3);
		obj1.add(9);
		obj1.add(1);
		obj1.add(5);
		obj1.add(7);

		/*
          3
        /   \
       1     7
            /  \ 
           5    9
            \
             6  
      inorder = 1,3,5,6,7,9
    */
		obj2.add(3);
		obj2.add(1);
		obj2.add(7);
		obj2.add(5);
		obj2.add(9);
		obj2.add(6);

		Console.Write("First Tree inorder  \n");
		obj1.inorder(obj1.root);

		Console.Write("\nSecond Tree inorder   \n");
		obj2.inorder(obj2.root);

		obj1.same_set(obj1.root, obj2.root);
	}
}

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
# Python 3 Program
# Check if two BST contain same set of elements

class Node :
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
    self.counter = 0
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def counter_nodes(self, head) :
    if (head != None) :
      return self.counter_nodes(head.left) + self.counter_nodes(head.right) + 1
    
    return 0
  
  def get_elements(self, head, auxiliary) :
    if (head != None) :
      self.get_elements(head.left, auxiliary)
      auxiliary[self.counter] += head.data
      self.counter += 1
      self.get_elements(head.right, auxiliary)
    
  
  def compare_element(self, head, auxiliary) :
    if (head != None) :
      self.compare_element(head.left, auxiliary)
      if (head.data == auxiliary[self.counter]) :
        self.counter += 1
      
      self.compare_element(head.right, auxiliary)
    
  
  def same_set(self, root1, root2) :
    if (root1 == None and root2 != None and root2 == None and root1 != None) :
      print("\nNo\n")
    else :
      size = self.counter_nodes(root1)
      if (size != self.counter_nodes(root2)) :
        print("\nNo\n")
        return
      
      auxiliary = [0]*size
      
      self.counter = 0
      self.get_elements(root1, auxiliary)
      self.counter = 0
      self.compare_element(root2, auxiliary)
      if (self.counter != size) :
        print("\nNo\n")
      else :
        print("\nYes\n")
      
    
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data ,end="  ")
      self.inorder(head.right)
    
  
def main() :
  obj1 = BinarySearchTree()
  obj2 = BinarySearchTree()

  #
  #          6
  #        /    \
  #       /      \
  #      3        9
  #     /  \      /
  #    1    5    7
  #    inorder = 1,3,5,6,7,9
  #  
  obj1.add(6)
  obj1.add(3)
  obj1.add(9)
  obj1.add(1)
  obj1.add(5)
  obj1.add(7)
  
  #
  #        3
  #      /   \
  #     1     7
  #          /  \
  #         5    9
  #          \
  #           6
  #    inorder = 1,3,5,6,7,9
  #  
  obj2.add(3)
  obj2.add(1)
  obj2.add(7)
  obj2.add(5)
  obj2.add(9)
  obj2.add(6)
  print("First Tree inorder  ")
  obj1.inorder(obj1.root)
  print("\nSecond Tree inorder   ")
  obj2.inorder(obj2.root)
  obj1.same_set(obj1.root, obj2.root)


if __name__ == "__main__":
  main()

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
# Ruby Program
# Check if two BST contain same set of elements

class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root, :counter
	attr_accessor :root, :counter
	def initialize() 
		@root = nil
		@counter = 0
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def counter_nodes(head) 
		if (head != nil) 
			return self.counter_nodes(head.left) + self.counter_nodes(head.right) + 1
		end
		return 0
	end
	def get_elements(head, auxiliary) 
		if (head != nil) 
			self.get_elements(head.left, auxiliary)
			auxiliary[self.counter] += head.data
			self.counter += 1
			self.get_elements(head.right, auxiliary)
		end
	end
	def compare_element(head, auxiliary) 
		if (head != nil) 
			self.compare_element(head.left, auxiliary)
			if (head.data == auxiliary[self.counter]) 
				self.counter += 1
			end
			self.compare_element(head.right, auxiliary)
		end
	end
	def same_set(root1, root2) 
		if (root1 == nil and root2 != nil and root2 == nil and root1 != nil) 
			print("\nNo\n")
		else 
			size = self.counter_nodes(root1)
			if (size != self.counter_nodes(root2)) 
				print("\nNo\n")
				return
			end
			auxiliary = Array.new(size,0)
			
			self.counter = 0
			self.get_elements(root1, auxiliary)
			self.counter = 0
			self.compare_element(root2, auxiliary)
			if (self.counter != size) 
				print("\nNo\n")
			else 
				print("\nYes\n")
			end
		end
	end
	def inorder(head) 
		if (head != nil) 
			self.inorder(head.left)
			print(head.data ,"  ")
			self.inorder(head.right)
		end
	end
end

def main() 
	obj1 = BinarySearchTree.new()
	obj2 = BinarySearchTree.new()

	#
	#          6
	#        /    \
	#       /      \
	#      3        9
	#     /  \      /
	#    1    5    7
	#    inorder = 1,3,5,6,7,9
	#  

	obj1.add(6)
	obj1.add(3)
	obj1.add(9)
	obj1.add(1)
	obj1.add(5)
	obj1.add(7)
	
	#
	#        3
	#      /   \
	#     1     7
	#          /  \
	#         5    9
	#          \
	#           6
	#    inorder = 1,3,5,6,7,9
	#  
	obj2.add(3)
	obj2.add(1)
	obj2.add(7)
	obj2.add(5)
	obj2.add(9)
	obj2.add(6)
	print("First Tree inorder  \n")
	obj1.inorder(obj1.root)
	print("\nSecond Tree inorder   \n")
	obj2.inorder(obj2.root)
	obj1.same_set(obj1.root, obj2.root)
end
main()

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
<?php
/*
 Php Program
 Check if two BST contain same set of elements
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;
  public $counter;

  function __construct() {
    $this->root = null;
    $this->counter = 0;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function counter_nodes($head) {
    if ($head != null) {
      return $this->counter_nodes($head->left) + $this->counter_nodes($head->right) + 1;
    }
    return 0;
  }
  public  function get_elements($head, &$auxiliary) {
    if ($head != null) {
      $this->get_elements($head->left, $auxiliary);
      $auxiliary[$this->counter] += $head->data;
      $this->counter++;
      $this->get_elements($head->right, $auxiliary);
    }
  }
  public  function compare_element($head, $auxiliary) {
    if ($head != null) {
      $this->compare_element($head->left, $auxiliary);
      if ($head->data == $auxiliary[$this->counter]) {
        $this->counter++;
      }
      $this->compare_element($head->right, $auxiliary);
    }
  }
  public  function same_set($root1, $root2) {
    if ($root1 == null && $root2 != null && $root2 == null && $root1 != null) {
      echo("\nNo\n");
    } else {
      $size = $this->counter_nodes($root1);
      if ($size != $this->counter_nodes($root2)) {
        echo("\nNo\n");
        return;
      }
      $auxiliary = array_fill(0, $size, 0);
  
      $this->counter = 0;
      $this->get_elements($root1, $auxiliary);
      $this->counter = 0;
      $this->compare_element($root2, $auxiliary);
      if ($this->counter != $size) {
        echo("\nNo\n");
      } else {
        echo("\nYes\n");
      }
    }
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo($head->data ."  ");
      $this->inorder($head->right);
    }
  }

}
function main() {
  $obj1 = new BinarySearchTree();
  $obj2 = new BinarySearchTree();
    /*
          6
        /    \
       /      \
      3        9
     /  \      / 
    1    5    7   

    inorder = 1,3,5,6,7,9
  */        
  $obj1->add(6);
  $obj1->add(3);
  $obj1->add(9);
  $obj1->add(1);
  $obj1->add(5);
  $obj1->add(7);
    /*
        3
      /   \
     1     7
          /  \ 
         5    9
          \
           6  
    inorder = 1,3,5,6,7,9
  */       
  $obj2->add(3);
  $obj2->add(1);
  $obj2->add(7);
  $obj2->add(5);
  $obj2->add(9);
  $obj2->add(6);
  echo("First Tree inorder  \n");
  $obj1->inorder($obj1->root);
  echo("\nSecond Tree inorder   \n");
  $obj2->inorder($obj2->root);
  $obj1->same_set($obj1->root, $obj2->root);
}
main();

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
/*
 Node Js Program
 Check if two BST contain same set of elements
*/

class Node {
	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {

	constructor() {
		this.root = null;
		this.counter = 0;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	counter_nodes(head) {
		if (head != null) {
			return this.counter_nodes(head.left) + this.counter_nodes(head.right) + 1;
		}
		return 0;
	}
	get_elements(head, auxiliary) {
		if (head != null) {
			this.get_elements(head.left, auxiliary);
			auxiliary[this.counter] += head.data;
			this.counter++;
			this.get_elements(head.right, auxiliary);
		}
	}
	compare_element(head, auxiliary) {
		if (head != null) {
			this.compare_element(head.left, auxiliary);
			if (head.data == auxiliary[this.counter]) {
				this.counter++;
			}
			this.compare_element(head.right, auxiliary);
		}
	}
	same_set(root1, root2) {
		if (root1 == null && root2 != null && root2 == null && root1 != null) {
			process.stdout.write("\nNo\n");
		} else {
			var size = this.counter_nodes(root1);
			if (size != this.counter_nodes(root2)) {
				process.stdout.write("\nNo\n");
				return;
			}
			var auxiliary = Array(size).fill(0);
			this.counter = 0;
			this.get_elements(root1, auxiliary);
			this.counter = 0;
			this.compare_element(root2, auxiliary);
			if (this.counter != size) {
				process.stdout.write("\nNo\n");
			} else {
				process.stdout.write("\nYes\n");
			}
		}
	}
	inorder(head) {
		if (head != null) {
			this.inorder(head.left);
			process.stdout.write(head.data + "  ");
			this.inorder(head.right);
		}
	}
}

function main() {
	var obj1 = new BinarySearchTree();
	var obj2 = new BinarySearchTree();
	/*
          6
        /    \
       /      \
      3        9
     /  \      / 
    1    5    7   

    inorder = 1,3,5,6,7,9
    */        
	obj1.add(6);
	obj1.add(3);
	obj1.add(9);
	obj1.add(1);
	obj1.add(5);
	obj1.add(7);
	/*
        3
      /   \
     1     7
          /  \ 
         5    9
          \
           6  
    inorder = 1,3,5,6,7,9
    */       
	obj2.add(3);
	obj2.add(1);
	obj2.add(7);
	obj2.add(5);
	obj2.add(9);
	obj2.add(6);
	process.stdout.write("First Tree inorder  \n");
	obj1.inorder(obj1.root);
	process.stdout.write("\nSecond Tree inorder   \n");
	obj2.inorder(obj2.root);
	obj1.same_set(obj1.root, obj2.root);
}


main();

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes
/*
  Swift 4 Program
  Check if two BST contain same set of elements
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  var counter: Int;
  init() {
    self.root = nil;
    self.counter = 0;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func counter_nodes(_ head: Node? ) -> Int{
    if (head != nil) {
      return self.counter_nodes(head!.left) + self.counter_nodes(head!.right) + 1;
    }
    return 0;
  }
  func get_elements(_ head: Node? , _ auxiliary : inout [Int] ) {
    if (head != nil) {
      self.get_elements(head!.left, &auxiliary);
      auxiliary[self.counter] += head!.data;
      self.counter += 1;
      self.get_elements(head!.right, &auxiliary);
    }
  }
  func compare_element(_ head: Node? , _ auxiliary : [Int] ) {
    if (head != nil) {
      self.compare_element(head!.left, auxiliary);
      if (head!.data == auxiliary[self.counter]) {
        self.counter += 1;
      }
      self.compare_element(head!.right, auxiliary);
    }
  }
  func same_set(_ root1: Node? , _ root2 : Node? ) {
    if (root1 == nil && root2 != nil && root2 == nil && root1 != nil) {
      print("\nNo\n");
    } else {
      let size: Int = self.counter_nodes(root1);
      if (size != self.counter_nodes(root2)) {
        print("\nNo\n");
        return;
      }
      var auxiliary: [Int] = Array(repeating:0,count:size);
      self.counter = 0;
      self.get_elements(root1, &auxiliary);
      self.counter = 0;
      self.compare_element(root2, auxiliary);
      if (self.counter != size) {
        print("\nNo\n");
      } else {
        print("\nYes\n");
      }
    }
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data ,terminator:"  ");
      self.inorder(head!.right);
    }
  }
}
func main() {
  let obj1: BinarySearchTree  = BinarySearchTree();
  let obj2: BinarySearchTree  = BinarySearchTree();
  /*
          6
        /    \
       /      \
      3        9
     /  \      / 
    1    5    7   

    inorder = 1,3,5,6,7,9
  */        
  obj1.add(6);
  obj1.add(3);
  obj1.add(9);
  obj1.add(1);
  obj1.add(5);
  obj1.add(7);

  /*
        3
      /   \
     1     7
          /  \ 
         5    9
          \
           6  
    inorder = 1,3,5,6,7,9
  */       
  obj2.add(3);
  obj2.add(1);
  obj2.add(7);
  obj2.add(5);
  obj2.add(9);
  obj2.add(6);
  print("First Tree inorder  ");
  obj1.inorder(obj1.root);
  print("\nSecond Tree inorder ");
  obj2.inorder(obj2.root);
  obj1.same_set(obj1.root, obj2.root);
}
main();

Output

First Tree inorder  
  1   3   5   6   7   9 
Second Tree inorder 
  1   3   5   6   7   9 
 Yes




Comment

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