{"id":"47a17377-3a10-4ca4-b6df-a30d3e144ab9","name":"Largest Bst Subtree","description":"1. You are given a partially written BinaryTree class.\r\n2. 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.\r\n3. Input is managed for you. \r\n\r\nNote -> Please refer the question video for clarity.","inputFormat":"Input is managed for you.","outputFormat":"<root of largest sub-tree which is a bst>@<number of nodes in the largest sub-tree which is a bst>","constraints":"Time complexity must be O(n)\r\nSpace should not be more than required for recursion (call-stack)","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data=0;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n class Pair {\n public:\n Node *node=nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n };\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\n\nvoid display(Node *node)\n{\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\n\n\nint height(Node *node)\n{\n return node == nullptr ? -1 : max(height(node->left), height(node->right)) + 1; \n}\n\n class bst{\n public:\n bool isbst = false;\n int max =0;\n int min=0;\n Node *root=nullptr;\n int size=0;\n};\n \n bst Bst(Node *node){\n \n if(node == nullptr)\n {\n bst bres;\n bres.isbst = true;\n bres.max = INT_MIN;\n bres.min = INT_MAX;\n return bres;\n }\n bst l = Bst(node->left);\n bst r = Bst(node->right);\n \n bst ans;\n \n ans.max = max(node->data, max(l.max,r.max));\n ans.min = min(node->data,min(l.min,r.min));\n \n if(l.isbst==true && r.isbst==true && (l.max < node->data && r.min > node->data)){\n ans.isbst=true;\n }\n \n // write your code here\n \n return ans;\n }\n\nint main(){\n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n \n Node *root = constructTree(arr);\n\n bst r = Bst(root);\n cout<<r.root->data<<\"@\"<<r.size;\n \n \n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n \r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n \r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n\ndef height(node):\n if(node == None):\n return -1\n else:\n ans = max(height(node.left),height(node.right))+1\n return ans\n \nclass bst:\n def __init__(self):\n self.isbst=False\n self.max= -math.inf\n self.min=math.inf\n self.root=None\n self.size=0\n \ndef Bst(node):\n if(node==None):\n bres=bst\n bres.isbst = True\n bres.max = -math.inf\n bres.min = math.inf\n bres.size = 0\n return bres\n \n l = Bst(node.left)\n r = Bst(node.right)\n ans=bst()\n \n ans.max = max(node.data,max(l.max,r.max))\n ans.min = min(node.data,min(l.min,r.min))\n \n if(l.isbst==True and r.isbst==True and (l.max<=node.data and r.min>node.data)):\n ans.isbst=True\n \n\n # write your code here\n \n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\nans=bst()\n\nroot = construct(arr)\nans = Bst(root)\n\nprint(ans.root.data,end=\"\")\nprint(\"@\",end=\"\")\nprint(ans.size)"}},"points":10,"difficulty":"medium","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"50@7\r\n","questionVideo":"https://www.youtube.com/embed/6KeiEYyPOPA","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"ae1a1ec9-1dd5-4891-88bc-e34ad12acf30","name":"Largest Bst Subtree","slug":"largest-bst-subtree","type":1}],"next":{"id":"f36d3b73-2af2-41ce-9ea5-f7f5223f0dcf","name":"Largest Bst Subtree","type":3,"slug":"largest-bst-subtree"},"prev":{"id":"0dc469c8-b7f3-4383-987e-3e5ab36dec82","name":"Is a Binary Search Tree","type":3,"slug":"is-a-binary-search-tree"}}}

Largest Bst Subtree

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 -> Please refer the question video for clarity.

{"id":"47a17377-3a10-4ca4-b6df-a30d3e144ab9","name":"Largest Bst Subtree","description":"1. You are given a partially written BinaryTree class.\r\n2. 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.\r\n3. Input is managed for you. \r\n\r\nNote -> Please refer the question video for clarity.","inputFormat":"Input is managed for you.","outputFormat":"<root of largest sub-tree which is a bst>@<number of nodes in the largest sub-tree which is a bst>","constraints":"Time complexity must be O(n)\r\nSpace should not be more than required for recursion (call-stack)","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data=0;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n class Pair {\n public:\n Node *node=nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n };\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\n\nvoid display(Node *node)\n{\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\n\n\nint height(Node *node)\n{\n return node == nullptr ? -1 : max(height(node->left), height(node->right)) + 1; \n}\n\n class bst{\n public:\n bool isbst = false;\n int max =0;\n int min=0;\n Node *root=nullptr;\n int size=0;\n};\n \n bst Bst(Node *node){\n \n if(node == nullptr)\n {\n bst bres;\n bres.isbst = true;\n bres.max = INT_MIN;\n bres.min = INT_MAX;\n return bres;\n }\n bst l = Bst(node->left);\n bst r = Bst(node->right);\n \n bst ans;\n \n ans.max = max(node->data, max(l.max,r.max));\n ans.min = min(node->data,min(l.min,r.min));\n \n if(l.isbst==true && r.isbst==true && (l.max < node->data && r.min > node->data)){\n ans.isbst=true;\n }\n \n // write your code here\n \n return ans;\n }\n\nint main(){\n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n \n Node *root = constructTree(arr);\n\n bst r = Bst(root);\n cout<<r.root->data<<\"@\"<<r.size;\n \n \n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n \r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n \r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n\ndef height(node):\n if(node == None):\n return -1\n else:\n ans = max(height(node.left),height(node.right))+1\n return ans\n \nclass bst:\n def __init__(self):\n self.isbst=False\n self.max= -math.inf\n self.min=math.inf\n self.root=None\n self.size=0\n \ndef Bst(node):\n if(node==None):\n bres=bst\n bres.isbst = True\n bres.max = -math.inf\n bres.min = math.inf\n bres.size = 0\n return bres\n \n l = Bst(node.left)\n r = Bst(node.right)\n ans=bst()\n \n ans.max = max(node.data,max(l.max,r.max))\n ans.min = min(node.data,min(l.min,r.min))\n \n if(l.isbst==True and r.isbst==True and (l.max<=node.data and r.min>node.data)):\n ans.isbst=True\n \n\n # write your code here\n \n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\nans=bst()\n\nroot = construct(arr)\nans = Bst(root)\n\nprint(ans.root.data,end=\"\")\nprint(\"@\",end=\"\")\nprint(ans.size)"}},"points":10,"difficulty":"medium","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"50@7\r\n","questionVideo":"https://www.youtube.com/embed/6KeiEYyPOPA","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"ae1a1ec9-1dd5-4891-88bc-e34ad12acf30","name":"Largest Bst Subtree","slug":"largest-bst-subtree","type":1}],"next":{"id":"f36d3b73-2af2-41ce-9ea5-f7f5223f0dcf","name":"Largest Bst Subtree","type":3,"slug":"largest-bst-subtree"},"prev":{"id":"0dc469c8-b7f3-4383-987e-3e5ab36dec82","name":"Is a Binary Search Tree","type":3,"slug":"is-a-binary-search-tree"}}}
plane

Editor

Loading...

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 -> Please refer the question video for clarity.

Constraints

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

Format

Input

Input is managed for you.

Output

@

Example

Sample Input

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

Sample Output

50@7

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode