Run ❯
Get your
own
website
×
Change Orientation
Change Theme, Dark/Light
Go to Spaces
Python
C
Java
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def inOrderTraversal(node): if node is None: return inOrderTraversal(node.left) print(node.data, end=", ") inOrderTraversal(node.right) def minValueNode(node): current = node while current.left is not None: current = current.left return current def delete(node, data): if not node: return None if data < node.data: node.left = delete(node.left, data) elif data > node.data: node.right = delete(node.right, data) else: # Node with only one child or no child if not node.left: temp = node.right node = None return temp elif not node.right: temp = node.left node = None return temp # Node with two children, get the in-order successor node.data = minValueNode(node.right).data node.right = delete(node.right, node.data) return node root = TreeNode(13) node7 = TreeNode(7) node15 = TreeNode(15) node3 = TreeNode(3) node8 = TreeNode(8) node14 = TreeNode(14) node19 = TreeNode(19) node18 = TreeNode(18) root.left = node7 root.right = node15 node7.left = node3 node7.right = node8 node15.left = node14 node15.right = node19 node19.left = node18 # Traverse inOrderTraversal(root) # Delete node 15 delete(root,15) # Traverse print() # Creates a new line inOrderTraversal(root) # Python
#include
#include
typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; TreeNode* createNode(int data) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } void inOrderTraversal(TreeNode* node) { if (node == NULL) { return; } inOrderTraversal(node->left); printf("%d, ", node->data); inOrderTraversal(node->right); } TreeNode* minValueNode(TreeNode* node) { TreeNode* current = node; while (current && current->left != NULL) { current = current->left; } return current; } TreeNode* delete(TreeNode* node, int data) { if (node == NULL) { return NULL; } if (data < node->data) { node->left = delete(node->left, data); } else if (data > node->data) { node->right = delete(node->right, data); } else { // Node with only one child or no child if (node->left == NULL) { TreeNode* temp = node->right; free(node); return temp; } else if (node->right == NULL) { TreeNode* temp = node->left; free(node); return temp; } // Node with two children: Get the inorder successor (smallest in the right subtree) TreeNode* temp = minValueNode(node->right); // Copy the inorder successor's content to this node node->data = temp->data; // Delete the inorder successor node->right = delete(node->right, temp->data); } return node; } int main() { TreeNode* root = createNode(13); root->left = createNode(7); root->right = createNode(15); root->left->left = createNode(3); root->left->right = createNode(8); root->right->left = createNode(14); root->right->right = createNode(19); root->right->right->left = createNode(18); // Traverse inOrderTraversal(root); printf("\n"); // Creates a new line // Delete node 15 root = delete(root, 15); // Traverse inOrderTraversal(root); printf("\n"); return 0; } // C
public class Main { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; this.left = null; this.right = null; } } public static void inOrderTraversal(TreeNode node) { if (node == null) { return; } inOrderTraversal(node.left); System.out.print(node.data + ", "); inOrderTraversal(node.right); } public static TreeNode minValueNode(TreeNode node) { TreeNode current = node; while (current.left != null) { current = current.left; } return current; } public static TreeNode delete(TreeNode node, int data) { if (node == null) { return null; } if (data < node.data) { node.left = delete(node.left, data); } else if (data > node.data) { node.right = delete(node.right, data); } else { // Node with only one child or no child if (node.left == null) { return node.right; } else if (node.right == null) { return node.left; } // Node with two children: Get the inorder successor node.data = minValueNode(node.right).data; node.right = delete(node.right, node.data); } return node; } public static void main(String[] args) { TreeNode root = new TreeNode(13); root.left = new TreeNode(7); root.right = new TreeNode(15); root.left.left = new TreeNode(3); root.left.right = new TreeNode(8); root.right.left = new TreeNode(14); root.right.right = new TreeNode(19); root.right.right.left = new TreeNode(18); // Traverse inOrderTraversal(root); System.out.println(); // Creates a new line // Delete node 15 delete(root, 15); // Traverse inOrderTraversal(root); } } // Java
Python result:
C result:
Java result:
3, 7, 8, 13, 14, 15, 18, 19,
3, 7, 8, 13, 14, 18, 19,
3, 7, 8, 13, 14, 15, 18, 19,
3, 7, 8, 13, 14, 18, 19,
3, 7, 8, 13, 14, 15, 18, 19,
3, 7, 8, 13, 14, 18, 19,