Largest Bst Subtree

medium

1. You are given a partially written BinaryTree class.
2. You are required to find the root of largest sub-tree which is a BST. Also, find the number of nodes in that sub-tree.
3. Input is managed for you. 

Note -&gt; Please refer the question video for clarity.

Input Format

Input is managed for you.

Output Format

Constraints

Time complexity must be O(n)
Space should not be more than required for recursion (call-stack)

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

15
50 25 12 n n 37 n n 75 62 n n 87 n n

Output

50@7

Is Balanced Tree

Related Questions

easy Size, Sum, Maximum And Height Of A Binary Tree easy Levelorder Traversal Of Binary Tree easy Iterative Pre, Post And Inorder Traversals Of Binary Tree easy Find And Nodetorootpath In Binary Tree easy Print K Levels Down easy Path To Leaf From Root In Range easy Transform To Left-cloned Tree easy Transform To Normal From Left-cloned Tree easy Print Single Child Nodes easy Remove Leaves In Binary Tree easy Print Nodes K Distance Away easy Diameter Of A Binary Tree easy Tilt Of Binary Tree easy Is A Binary Search Tree easy Is Balanced Tree