how to traverse a array represented binary tree using only a father field

[Premal Mishra]

How to traverse a binary tree whose nodes only contain a father field. e.g.

struct NodeType {
int data;
int father;
};

A left son's father field has a negative value and right son's father field has +ve value. Absolute value of the father field points to the father of the node.
Such tree can be traversed only in an upward direction but i cannot reach all nodes starting at a leaf. Once all nodes reachable from a leaf are traversed, i get stuck. What i can make out is that while constructing the tree, i will need to keep track of more than just one leaf so that i can traverse all nodes of the binary tree

Want to know an algorthm for this

Am tryng to solve a data-structure exercise in aarom m. tenebaum --5.2.4

[iohos]

dis mite be a lengthy solution....... do u need d whole algorithm or just d remedial soln

[iohos]

struct TreeNode
{
struct TreeNode *lgame;
int data;
struct TreeNode *rgame;
};
typedef struct TreeNode TreeNode;

[Premal Mishra]

@iohos
Dynamic representation is not to be used.

struct NodeType {
int data;
int father;
};

How to traverse a binary tree wherein each node is as shown above

Initial problem specification is to convert a binary tree represented using nodeType as i have shown to a binary tree using nodeType as you have shown.

[iohos]

ok, wrking on it. will post it soon

[jkmyoung]

1. Create a node array of same length as your initial array.
2. For each array element, create a node. Set the values to be the same, but initially set all children to null.
3. Go back through the array.
4. Set each node's children accordingly. Eg, if the first array with your NodeType is A, and the second array with the other node is A2:

foreach node in A
{
get parent index
determine if we are left or right child by comparing values.
set A2[parent_index] corresponding child accordingly.
}

[Premal Mishra]

hi jkm,
thank u for the solution. its simple & good.

sorry abt the delayed response

Regards