Problem: Given a Binary Search Tree and a value key. Remove the node from tree whose value is equal to the given key.
Approach: You can refer the Binary Search Tree section for approach. I am just giving implementation in C#.
Implementation in C#:
public void Remove(int key)
{
if (this.Root != null)
{
this.Root = this.RemoveNode(this.Root, key);
}
}
private BinaryTreeNode RemoveNode(BinaryTreeNode node, int key)
{
if (node == null)
{
return null;
}
if (key < node.Value)
{
node.LeftNode = this.RemoveNode(node.LeftNode, key);
}
else if (key > node.Value)
{
node.RightNode = this.RemoveNode(node.RightNode, key);
}
else
{
if (node.RightNode == null)
{
return node.LeftNode;
}
else if (node.LeftNode == null)
{
return node.RightNode;
}
else
{
node.Value = this.FindMin(node.RightNode);
node.RightNode = this.RemoveNode(node.RightNode, node.Value);
}
}
return node;
}
private int FindMin(BinaryTreeNode node)
{
while(node.LeftNode != null)
{
node = node.LeftNode;
}
return node.Value;
}
Complexity: O(h) where h is height of the tree
No comments:
Post a Comment