4242,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 22:I[12820,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 23:I[15024,["/_next/static/chunks/0da1bbecd1c48715.js","/_next/static/chunks/088ad42761043d79.js"],"default"] 24:Tda3,

Problem

Given a Binary Search Tree (BST) that may contain duplicate values, remove all duplicate nodes so that every value appears only once in the tree. The resulting tree should remain a valid BST.

Examples

Example 1

Input:  [1,2,2,3,4,4,4,5]  (BST with inorder traversal: 1 2 2 3 4 4 4 5)
Output: [1,2,3,4,5]         (BST with inorder traversal: 1 2 3 4 5)
Explanation: All duplicate nodes are removed, only unique values remain.

Constraints

The BST may contain duplicate values.
The operation must be done in-place.

Solution

Method 1 - Inorder Traversal & Remove

Intuition

Duplicates in a BST appear as consecutive nodes in an inorder traversal. By tracking the previous node, we can detect and remove duplicates efficiently.

Approach

Traverse the BST in-order. If the current node's value equals the previous node's value, remove the current node and continue. Otherwise, update the previous node and proceed.

Complexity

Time Complexity: O(N), where N is the number of nodes in the BST (each node is visited once).
Space Complexity: O(H), where H is the height of the tree (due to recursion stack).

Code

[{"language":"C++","code":"#include <iostream>\nusing namespace std;\n\nstruct TreeNode {\n    int val;\n    TreeNode *left, *right;\n    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\n\nclass Solution {\npublic:\n    TreeNode* removeDuplicates(TreeNode* root) {\n        TreeNode* prev = nullptr;\n        return removeDup(root, prev);\n    }\nprivate:\n    TreeNode* removeDup(TreeNode* node, TreeNode*& prev) {\n        if (!node) return nullptr;\n        node->left = removeDup(node->left, prev);\n        if (prev && prev->val == node->val) {\n            TreeNode* right = removeDup(node->right, prev);\n            delete node;\n            return right;\n        }\n        prev = node;\n        node->right = removeDup(node->right, prev);\n        return node;\n    }\n};","lang":"cpp"},{"language":"Java","code":"class TreeNode {\n    int val;\n    TreeNode left, right;\n    TreeNode(int x) { val = x; }\n}\n\nclass Solution {\n    private TreeNode prev = null;\n    public TreeNode removeDuplicates(TreeNode root) {\n        return removeDup(root);\n    }\n    private TreeNode removeDup(TreeNode node) {\n        if (node == null) return null;\n        node.left = removeDup(node.left);\n        if (prev != null && prev.val == node.val) {\n            return removeDup(node.right);\n        }\n        prev = node;\n        node.right = removeDup(node.right);\n        return node;\n    }\n}","lang":"java"},{"language":"Python","code":"class TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nclass Solution:\n    def removeDuplicates(self, root):\n        self.prev = None\n        return self._removeDup(root)\n    def _removeDup(self, node):\n        if not node:\n            return None\n        node.left = self._removeDup(node.left)\n        if self.prev and self.prev.val == node.val:\n            return self._removeDup(node.right)\n        self.prev = node\n        node.right = self._removeDup(node.right)\n        return node","lang":"python"}]

19:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justify-between gap-4","children":[["$","h1",null,{"className":"text-4xl font-bold tex

Related Tags