{"id":"48df72c8-8769-4342-bef7-e467e92f0ebc","name":"Remove Node From Bst","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of remove function. \"remove\" function is expected to remove a new node with given data to the tree and return the new root.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video to figure out the algorithm required for deletion. It specifies some requirements of the question as well.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\nvoid display(Node* node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \" <- \" + to_string(node->data) + \" -> \";\n\n string left = (node->left == nullptr) ? \".\" : \"\" + to_string(node->left->data);\n string right = (node->right == nullptr) ? \".\" : \"\" + to_string(node->right->data);\n\n str = left + str + right;\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nint max(Node* root){\n if(root->right== nullptr){\n return root->data;\n }\n return max(root->right);\n}\n\n\nNode* remove(Node* root,int data){\n// Write your code here\n}\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n,0);\n for(int i=0;i<n;i++){\n string x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n int data;\n cin >> data;\n Node* root= construct(arr);\n \n root=remove(root,data);\n\n display(root);\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 Node remove(Node node, int data) {\r\n // write your code here\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 int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n root = remove(root, data);\r\n\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.data = key\n \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 while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n else:\n st.pop();\n return root; \n \n \ndef display(node) :\n if (node == None):\n return;\n \n s = \" <- \" + str(node.data) + \" -> \";\n left = \".\" if node.left is None else \"\"+str(node.left.data);\n right = \".\" if node.right is None else \"\" + str(node.right.data);\n \n s=left + s + right;\n print(s);\n \n display(node.left);\n display(node.right);\n \n \ndef maxs(node):\n if node.right is None:\n return node.data\n \n return maxs(node.right)\n \n \ndef removeNode(root, data):\n# Write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nval=int(input())\n\nroot=construct(arr)\n\nroot = removeNode(root, val)\ndisplay(root)"}},"points":10,"difficulty":"medium","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n\r\n62","sampleOutput":"25 <- 50 -> 75\r\n12 <- 25 -> 37\r\n. <- 12 -> .\r\n. <- 37 -> .\r\n. <- 75 -> 87\r\n. <- 87 -> .","questionVideo":"https://www.youtube.com/embed/3_7me98ivvw","hints":[],"associated":[{"id":"8bc65b52-4d8f-4bb2-971f-f5b10808c8f4","name":"In BST each node has a key that must be smaller than all keys in its left-hand child's subtree and greater than all keys in its right-hand child's subtree.","slug":"in-bst-each-node-has-a-key-that-must-be-smaller-than-all-keys-in-its-left-hand-child-s-subtree-and-greater-than-all-keys-in-its-right-hand-child-s-subtree","type":4},{"id":"98f36c7d-2e67-4f03-afc6-3420a4d45031","name":"For a node with two children, the node to be removed is recursively replaced with its in-order successor or predecessor until the node value is placed on the tree's leaf.","slug":"for-a-node-with-two-children-the-node-to-be-removed-is-recursively-replaced-with-its-in-order-successor-or-predecessor-until-the-node-value-is-placed-on-the-tree-s-leaf","type":4},{"id":"d1382ee0-175d-473a-bc93-0d497e7ca568","name":"Fill in the missing line to complete the pseudocode for searching a node in BST :","slug":"fill-in-the-missing-line-to-complete-the-pseudocode-for-searching-a-node-in-bst","type":4}],"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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"8547fb11-d692-4f58-95bd-0fcee5e4e14b","name":"Remove Node From Bst","slug":"remove-node-from-bst","type":1}],"next":{"id":"5879bce5-4ee0-4dec-903f-c729ac5b36be","name":"Remove Node from BST","type":3,"slug":"remove-node-from-bst"},"prev":{"id":"e80522bf-dde1-4379-bcb2-ed182f33bb4c","name":"Add Node to BST","type":3,"slug":"add-node-to-bst"}}}

Remove Node From Bst

1. You are given a partially written BST class. 2. You are required to complete the body of remove function. "remove" function is expected to remove a new node with given data to the tree and return the new root. 3. Input and Output is managed for you. Note -> Please watch the question video to figure out the algorithm required for deletion. It specifies some requirements of the question as well.

{"id":"48df72c8-8769-4342-bef7-e467e92f0ebc","name":"Remove Node From Bst","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of remove function. \"remove\" function is expected to remove a new node with given data to the tree and return the new root.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video to figure out the algorithm required for deletion. It specifies some requirements of the question as well.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\nvoid display(Node* node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \" <- \" + to_string(node->data) + \" -> \";\n\n string left = (node->left == nullptr) ? \".\" : \"\" + to_string(node->left->data);\n string right = (node->right == nullptr) ? \".\" : \"\" + to_string(node->right->data);\n\n str = left + str + right;\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nint max(Node* root){\n if(root->right== nullptr){\n return root->data;\n }\n return max(root->right);\n}\n\n\nNode* remove(Node* root,int data){\n// Write your code here\n}\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n,0);\n for(int i=0;i<n;i++){\n string x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n int data;\n cin >> data;\n Node* root= construct(arr);\n \n root=remove(root,data);\n\n display(root);\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 Node remove(Node node, int data) {\r\n // write your code here\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 int data = Integer.parseInt(br.readLine());\r\n\r\n Node root = construct(arr);\r\n root = remove(root, data);\r\n\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.data = key\n \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 while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\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 top.state+=1\n else:\n st.pop();\n return root; \n \n \ndef display(node) :\n if (node == None):\n return;\n \n s = \" <- \" + str(node.data) + \" -> \";\n left = \".\" if node.left is None else \"\"+str(node.left.data);\n right = \".\" if node.right is None else \"\" + str(node.right.data);\n \n s=left + s + right;\n print(s);\n \n display(node.left);\n display(node.right);\n \n \ndef maxs(node):\n if node.right is None:\n return node.data\n \n return maxs(node.right)\n \n \ndef removeNode(root, data):\n# Write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nval=int(input())\n\nroot=construct(arr)\n\nroot = removeNode(root, val)\ndisplay(root)"}},"points":10,"difficulty":"medium","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n\r\n62","sampleOutput":"25 <- 50 -> 75\r\n12 <- 25 -> 37\r\n. <- 12 -> .\r\n. <- 37 -> .\r\n. <- 75 -> 87\r\n. <- 87 -> .","questionVideo":"https://www.youtube.com/embed/3_7me98ivvw","hints":[],"associated":[{"id":"8bc65b52-4d8f-4bb2-971f-f5b10808c8f4","name":"In BST each node has a key that must be smaller than all keys in its left-hand child's subtree and greater than all keys in its right-hand child's subtree.","slug":"in-bst-each-node-has-a-key-that-must-be-smaller-than-all-keys-in-its-left-hand-child-s-subtree-and-greater-than-all-keys-in-its-right-hand-child-s-subtree","type":4},{"id":"98f36c7d-2e67-4f03-afc6-3420a4d45031","name":"For a node with two children, the node to be removed is recursively replaced with its in-order successor or predecessor until the node value is placed on the tree's leaf.","slug":"for-a-node-with-two-children-the-node-to-be-removed-is-recursively-replaced-with-its-in-order-successor-or-predecessor-until-the-node-value-is-placed-on-the-tree-s-leaf","type":4},{"id":"d1382ee0-175d-473a-bc93-0d497e7ca568","name":"Fill in the missing line to complete the pseudocode for searching a node in BST :","slug":"fill-in-the-missing-line-to-complete-the-pseudocode-for-searching-a-node-in-bst","type":4}],"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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"8547fb11-d692-4f58-95bd-0fcee5e4e14b","name":"Remove Node From Bst","slug":"remove-node-from-bst","type":1}],"next":{"id":"5879bce5-4ee0-4dec-903f-c729ac5b36be","name":"Remove Node from BST","type":3,"slug":"remove-node-from-bst"},"prev":{"id":"e80522bf-dde1-4379-bcb2-ed182f33bb4c","name":"Add Node to BST","type":3,"slug":"add-node-to-bst"}}}
plane

Editor

Loading...

Remove Node From Bst

medium

1. You are given a partially written BST class. 2. You are required to complete the body of remove function. "remove" function is expected to remove a new node with given data to the tree and return the new root. 3. Input and Output is managed for you. Note -> Please watch the question video to figure out the algorithm required for deletion. It specifies some requirements of the question as well.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

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

Sample Output

25

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode