Deletion of a node from a binary search tree, Data Structure & Algorithms

Assignment Help:

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered.

If the node to be deleted contains no sons, then it might be deleted without further adjustment to the tree.
If the node to be deleted contains only one subtree, then its only son may be moved up to take its space.
The node p to be deleted contain two subtrees, then its inorder successor s have to take its place. The inorder successor could not contain left subtree. Hence, right son of s can be moved up to gain the place of s.

Example: Assume the following cases wherein node 5 have to be deleted.

1. The node to be deleted has no children.

2390_Deletion of a node from a Binary Search Tree.png

3. The node to be deleted contains two children. This case is complicated. The order of the binary tree has to be kept intact.

Related Discussions:- Deletion of a node from a binary search tree

Defination, what is an algorithms

what is an algorithms

Discrete time simulation of a queue, In this project you will write a progr...

In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Define heap, HEAP A heap is described to be a binary tree with a key i...

HEAP A heap is described to be a binary tree with a key in every node, such that 1-All the leaves of the tree are on 2 adjacent levels. 2- All leaves on the lowest leve

Two broad classes of collision resolution techniques, Two broad classes of ...

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

In order post order, illlustraate the construction of tree of a binary tree...

illlustraate the construction of tree of a binary tree given its in order and post order transversal

Asymptotic notation, Asymptotic notation Let us describe a few function...

Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

Test whether a binary tree is a binary search tree, Q. Write down an algori...

Q. Write down an algorithm to test whether a Binary Tree is a Binary Search Tree. A n s . The algorithm to check whether a Binary tree is as Binary Search

Tree traversals, There are three kinds of tree traversals, namely, Postorde...

There are three kinds of tree traversals, namely, Postorder , Preorder and Inorder. Preorder traversal: Each of nodes is visited before its children are visited; first the roo

Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi...

1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages