FOR FREE MATERIALS

Introduction:

A binary tree is a special tree, where every node can have at most two children. One node designated as the root marks the beginning of the binary tree. In a binary tree, the child node on the left is called ‘left child node’ and the child node on the right is called the ‘right child node’.

A binary tree can either be empty or it may comprise a node called the ‘root’, a left sub-binary tree and right sub-binary tree, both of which acts like a binary tree.

Search:

When a node is to be searched in a binary tree, at first the tree is traversed using any traversal technique and while traversing, it is thoroughly checked whether the current node matches the given node that is being searched. If a match is found then stop the search or else keep on searching for the node in the right and left sub-trees of the current node until no nodes are left to be traversed in the binary tree.

Deletion:

In a binary tree the nodes do not have any order, so whenever a node is to be deleted, it is replaced with the deepest rightmost node in the binary tree.

Let us consider the binary tree in Fig 2 and the node to be deleted is 20. Thus the node 20 is replaced with the deepest rightmost node in the tree i.e. 50. Fig 3 represents how the binary tree will look like after deletion.

Algorithm:

Input: 

root which points to the root of the binary tree.

Output:

(a) Binary tree creation. 

(b) Printing the binary tree in in-order, post-order and pre-order. 

(c) Searching a node in the binary tree.

(d) Deleting a node from the binary tree.

Algo:

Step 1: Start

Step 2: Defining the create() function

l  Enter the value of the node.

l  Set temp[data] < = value .

l  If left child of the node exists then,

(a) Set temp[left] <= create().

l  If right child of the node exists then,

(a) Set temp[right]  <= create().

l  Return temp.

Step 3: Defining the preorder(temp) function

l If temp != NULL then,

(a) Display temp[data].

(b) Call preorder(temp[left]).

(c) Call preorder(temp[right]).

Step 4: Defining the inorder(temp) function

l If temp != NULL then,

(a) Call inorder(temp[left]).

(b) Display temp[data].

(c) Call inorder(temp[right]).

Step 5: Defining the postorder(temp) function

l If temp != NULL then,

(a) Call postorder(temp[left]).

(b) Call postorder(temp[right]).

(c) Display temp[data].

Step 6: Defining the deleteNode(root,value) function

l If root=NULL then,

(a) Return root.

l  If root[left]=NULL and root[right]=NULL then,

(a) If root[data]=value then,

Return NULL.

(b) Else then,

Return root.

l queue.insert(root).

l Set v_node <=  NULL

l  Repeat substepsuntill queue is not empty

(a)

Set temp   queue.delete().

(b) If temp[data]=value then,

Set v_node <=  

(c) If temp[left]!=NULL then,

queue.insert(temp[left])

(d) If temp[right]!=NULL then,

queue.insert(temp[right])

l  If v_node !=NULL then

(a) Set v     <=

(b) Call deepestDelete(root,temp).

(c) Set v_node[data]   <= v.

(d) 

(e) 

(f) 

(g) 

(h) 

(i) 

(j) 

(k) 

(l) 

(m) 

(n) 

(o) 

(p) 

(q) 

(r) 

(s) 

(t) 

(u) ,

l Return root.

Step 7: Defining the deepestDelete(root,d) function

l queue.insert(root).

l  Repeat substeps until queue is empty.

(a) Set temp <= queue .delete().

(b) If temp=d then,

Set temp  <= NULL

Return.

(c) If temp[right]!=NULL then,

If temp[right]=d

Set temp[right] <=  NULL.

Return.

Else then,

queue.insert(temp[right]).

(d) If temp[left]!=NULL then,

If temp[left]=d

Set temp[left] <= NULL .

Return.

Else then,

queue.insert(temp[left]).

Step 8: Defining the search(temp,value) function

l  If temp=NULL then,

(a) Return 0.

l  If temp[data]=value then,

(a) Return 1.

l 

 Set left    <= search(temp[left],value).

l  If left=1 then,

(a) Return 1.

l 

 Set right     <=  search(temp[right],value).

l  Return right.

Step 9: Stop