0
$\begingroup$

I would like to confirm below understanding,

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

enter image description here

Insertion:

In binary trees, a new node before insert has to specify 1) whose child it is going to be 2) mention whether new node goes as left/right child. For example(below image),

enter image description here


To add a new node to leaf node, a new node should also mention whether new node goes as left/right child.


Deletion:

For deletion, only certain nodes in a binary tree can be removed unambiguously.

Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

In a binary tree, a node with two children cannot be deleted unambiguously.


Is this understanding correct ?

$\endgroup$
1
$\begingroup$

Its hard to say without the knowledge of why a node goes to the left or right of another, and if this carries as a property throughout the tree. If by ambiguously you mean there is more then one valid way of replacing the node and the tree has an ordering structure (such as a binary search tree) then your understanding is correct. The deleted verticie can be replaced with either its in order predecessor, or its in order successor. Both of these will be valid with the ordering property.

$\endgroup$
  • $\begingroup$ ambiguously I mean more than one way $\endgroup$ – overexchange Jan 10 '17 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.