We can test whether a node ‘m’ is a proper ancestor of a node ‘n’ by testing whether ‘m’ precedes ‘n’ in X-order but follows ‘n’ in Y-order, where X and Y are chosen from {pre, post, in}. Determine all those pairs X and Y for which this statement holds.

SOLUTION :

[A] ALGORITHM -> PRE - ORDER :

Preorder(ptr)

If (ptr != NULL) then

Process to info[ptr]

Preorder(Link[Left])

Preorder(Link[Right])

Endif

Exit

Preorder traversal is mn

Postorder traversal is nm

[B] ALGORITHM -> POST - ORDER :

Postorder(ptr)

If (ptr != NULL) then

Postorder (Link[Left])

Process to info [ptr]

Postorder(Link[Right])

Endif

Exit

Preorder traversal is mn

Inorder traversal is nm

C] ALGORITHM -> IN - ORDER :

Inorder(ptr)

If (ptr != NULL) then

Inorder (Link[Left])

Process to info [ptr]

Inorder(Link[Right])

Endif

Exit

Inorder traversal is mn

Postorder traversal is nm

The following tree explains the complete traversal of the preorder, Inorder, Postorder

IPRE-ORDER TRAVERSAL – would be ABDEMN
IN-ORDER TRAVERSAL -- would be DBEAMN
POST-ORDER TRAVERSAL – would be DEBNMA

--------------------------------------------------------------------------------

OR*

Contributed by anantha lakshmi

1) We can test whether a node ‘m’ is a proper ancestor of a node ‘n’ by testing whether ‘m’ precedes ‘n’ in X-order but follows ‘n’ in Y-order, where X and Y are chosen from{pre, post, in}. Determine all those pairs X and Y for which this statement holds.

Solution:

Before we go into the question directly it would be easy for us to understand the basic concept about what are trees, node, traversing & kind of traversing. So a brief explanation of all are cited below for better understanding.

Tree:

A tree is a finite set of one or more nodes such that

(i) There is a specially designated node called the root;

(ii) The remaining nodes are partitioned into n>= disjoint sets T1,T2…Tn where each of these sets is a tree. T1,T2…Tn are called subtrees of the root.

Node:

A node stands for the item of information plus the branches to other items. The following diagram would explain better. The tree below had 12 nodes each item of data being a single letter for convenience. The level of a node is defined by initially letting the root be at level one. If a node is at level l then its children are at level l+1. You can understand it more better as you correlate with the below given figure.

A Sample Tree

The root is A and we will normally draw trees with the root at the top. The number of subtrees of a node is called a degree. The degree zero are called leaf or terminal node. The degree of A is 3, degree of C is 1 and of F is 0. Nodes that have zero degree are called leaf or terminal node. {K, L, F, G, M, I, J} is a set of leaf nodes. Alternatively the other nodes are referred as non terminals. The root of the subtrees of a node X are the children of X. X is the parent of its children. This children of D are H, I, J, the parent of D is A. Children of the same parent is called as siblings. H, I, J are siblings. We can extend this terminology if we need to so that we can ask for the grandparent of M which is D etc. The degree of a tree is maximum degree of the nodes in the tree. For the above tree the degree is 3.The ancestor of a node are all the nodes along the path from the root to that node. The ancestors of M are A, D, H.

Binary Tree Traversal
There are many operations that are often performed on trees. One notion that arises frequently is the idea of traversing a tree or visiting each node in the tree exactly once. Traversing is of three types they are
(i) Pre-Order Traversing
(ii) In-Order Traversing
(iii) Post-Order Traversing

Pre-Order:

The sequence of the nodes is root node followed by the child nodes taken in left to right order

In-Order:
Listing method in which the sequence of the nodes is left most child node, root node followed by remaining child nodes in a left to right order

Post-Order:
The sequence of the nodes is child notes in left to right followed by the root

For better understanding I have dealed with two diagram which states about what is node root and the child node. The diagram is so easy that you can merely understand the concept on looking at it.

Diagram 1:

In the above diagram
M is the Root Node
P is the Left Child Node
N is the Right Child Node

Pre-Order : MPN
In-Order : PMN
Post-Order : PNM

Diagram 2:

M is the Root Node
N is the Left Child Node
P is the Right Child Node
Pre-Order: MNP
In-Order: NMP
Post-Order: NPM

These are the pairs of X & Y available in Pre,In,Post
If N is a right node:
X = Pre order, inorder
Y = Post order
If N is a left node:
X = Pre order
Y = In order,Post order
Thus we can test whether a node ‘m’ is a proper ancestor of a node ‘n’ by testing whether ‘m’ precedes ‘n’ in X-order but follows ‘n’ in Y-order, where X and Y are chosen from{pre, post, in}. We can also determine the pairs of X and Y.

* = Laynetworks Note: We don't want to disappoint both the contributors though the combination of both is required for better marks. We appreciate all our contributors.

NEXT - 2) Consider a directed acyclic graph (dag) with ‘e’ arcs and with two distinguished vertices ‘s’ to ‘t’. By maximal, we mean no additional path may be added, but it doesnot mean that it is the largest size such set.