eolymp
bolt
Try our new interface for solving problems
Problems

Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

Time limit 1 second
Memory limit 128 MiB

Given an array of integers. Create a Binary Search Tree from these numbers. If the inserted value equals to the current node, insert it to the right subtree.

Write a method MaxDepth that finds the maximum depth of a tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

prb7463.gif

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 MaxDepth(void); // return the maximum depth of Binary Search Tree
};
// 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 maxDepth() // return the maximum depth of Binary Search Tree
}

You can create (use) additional methods if needed.

Input data

The first line contains number n (1n100). The second line contains n integers.

Output data

Create the Binary Search Tree from input data. Find and print its maximum depth.

Examples

Input example #1
6
14 9 1 14 20 13
Output example #1
3
Author Mykhailo Medvediev
Source C++ / Java Language