Same Tree#7465

Same Tree

1 second

128 megabytes

Very easy

Given two arrays of integers. Create two Binary Search Trees from these numbers. If the inserted value equals to the current node, insert it to the right subtree.

Write a method IsSameTree that checks if two trees are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Write the code according to the next interface:

// C, C++
class TreeNode
{
public:
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree
{
public:
  TreeNode *head;
  Tree() : head(NULL) {};
  void Insert(int val); // Insert number val into Binary Search Tree
  int IsSameTree(Tree *p); // return 1 if current Binary Search Tree equals to p, otherwise return 0
};

C++

// Java
class TreeNode
{
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x)
  {
    val = x;
    left = null;
    right = null;
  }
}

class Tree
{
  TreeNode head;
  Tree();
  void Insert(int val); // Insert number val into Binary Search Tree
  int IsSameTree(Tree p); // return 1 if current Binary Search Tree equals to p, otherwise return 0
}

Java

You can create (use) additional methods if needed.

Input

The first line contains number $n$ ( $1 \leq n \leq 100$ 1 \le n \le 100). The second line contains $n$ integers.

The third line contains number $m$ ( $1 \leq m \leq 100$ 1 \le m \le 100). The fourth line contains $m$ integers.

Output

Create two Binary Search Trees from input data. Print $1$ if they are the same and $0$ otherwise.

Examples

Example 1