Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.<\/p>\n
Basically, the deletion can be divided into two stages:<\/p>\n
Search for a node to remove.
\nIf the node is found, delete the node.
\nNote: Time complexity should be O(height of tree).<\/p>\n
Example:<\/p>\n
root = [5,3,6,2,4,null,7]
\nkey = 3<\/p>\n
5
\n \/ \\
\n 3 6
\n \/ \\ \\
\n2 4 7<\/p>\n
Given key to delete is 3. So we find the node with value 3 and delete it.<\/p>\n
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.<\/p>\n
5
\n \/ \\
\n 4 6
\n \/ \\
\n2 7<\/p>\n
Another valid answer is [5,2,6,null,4,null,7].<\/p>\n
5
\n \/ \\
\n 2 6
\n \\ \\
\n 4 7
\nAccepted
\n66,103
\nSubmissions
\n165,217<\/p>\n
\r\n\r\n\/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n *\/\r\n\/**\r\n * @param {TreeNode} root\r\n * @param {number} key\r\n * @return {TreeNode}\r\n *\/\r\nvar deleteNode = function(root, key) {\r\n\r\n var node = root;\r\n var nodeParent = root;\r\n var childReference = null;\r\n \r\n \/\/Find the node with key\r\n while(node !== null){\r\n if(node.val === key){\r\n break;\r\n } \r\n else if(node.val < key){\r\n nodeParent = node;\r\n node = node.right;\r\n childReference = 'right';\r\n }\r\n else{\r\n nodeParent = node;\r\n node = node.left;\r\n childReference = 'left';\r\n }\r\n } \r\n \r\n \/\/If node is not in the tree\r\n if(node === null) return root;\r\n \r\n \/\/If node is a leaf\r\n if(node.left === null && node.right === null){\r\n if(childReference === null) return null;\/\/Root node matches the key\r\n nodeParent[childReference] = null; \r\n }\r\n \/\/If node is has one child\r\n else if(node.left === null){\r\n if(childReference === null) return node.right;\/\/Root node matches the key\r\n nodeParent[childReference] = node.right;\r\n \r\n }\r\n else if(node.right === null){\r\n if(childReference === null) return node.left;\/\/Root node matches the key\r\n nodeParent[childReference] = node.left;\r\n }\r\n \/\/If node is has both children\r\n else{\r\n var value = findMinNode(node.right); \r\n node.val = value;\r\n node.right = deleteNode(node.right,value);\r\n }\r\n\r\n return root;\r\n \r\n};\r\n\r\nvar findMinNode = function(node){\r\n if(node === null) return false;\r\n while(node.left !== null){\r\n node = node.left;\r\n }\r\n return node.val;\r\n}\r\n\r\n<\/pre>\nI spent the whole morning on this and this is the result I got from the leetcode:<\/b><\/p>\n
Runtime: 92 ms, faster than 86.76% of JavaScript online submissions for Delete Node in a BST.<\/p>\n
Memory Usage: 42.2 MB, less than 32.28% of JavaScript online submissions for Delete Node in a BST.<\/p>\n","protected":false},"excerpt":{"rendered":"