`{"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);\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, 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,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=*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);\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, 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,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=*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"}}}` Editor

# 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.

None

## Format

### Input

Input is managed for you

### Output

Output is managed for you

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}15 50 25 12 n n 37 n n 75 62 n n 87 n n 62```

### Sample Output

`.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}25 `

Question Video

Discussions

Show Discussion

Related Resources 