# Algorithm related to Tree data structure

Anubrato Roy

Greenhorn

Posts: 3

posted 4 years ago

Hello All,

I am trying to come up with an algorithm for a Tree as follows -

I have a set of parent-child relationships defined (please see attached file). For each relationship, the parent objct is a node on the tree and all its children are immediate neighbours of this node, as in any tree.

Now, I want to validate a 'sequence' for the tree nodes, which works as following.

Arbitrary 'sequence' numbers are assigned to each node e.g. A=1, B=2, D=3, C=4, F=5, E=6. Now, I want to 'validate' this sequence. The sequence is valid if for every node, all its parent nodes have a lower sequence number than itself.

For example, if for node C, both B and A are parents, then these sequences are valid: A=1, B=2, C=3 or A=2, B=1, C=3.

In the attached diagram, for example, the node A has children B and C. B has children D and E while C has only one child F.

Now, the following sequences are examples of 'valid' sequences -

1. A=1, B=2, C=3, D=4, E=5, F=6

2. A=1, B=2, D=3, C=4, F=5, E=6

1. A=1, C=2, F=3, B=4, D=5, E=6

Can anyone please suggest an efficient algorithm to achieve this?

Regards,

Anubrato

I am trying to come up with an algorithm for a Tree as follows -

I have a set of parent-child relationships defined (please see attached file). For each relationship, the parent objct is a node on the tree and all its children are immediate neighbours of this node, as in any tree.

Now, I want to validate a 'sequence' for the tree nodes, which works as following.

Arbitrary 'sequence' numbers are assigned to each node e.g. A=1, B=2, D=3, C=4, F=5, E=6. Now, I want to 'validate' this sequence. The sequence is valid if for every node, all its parent nodes have a lower sequence number than itself.

For example, if for node C, both B and A are parents, then these sequences are valid: A=1, B=2, C=3 or A=2, B=1, C=3.

In the attached diagram, for example, the node A has children B and C. B has children D and E while C has only one child F.

Now, the following sequences are examples of 'valid' sequences -

1. A=1, B=2, C=3, D=4, E=5, F=6

2. A=1, B=2, D=3, C=4, F=5, E=6

1. A=1, C=2, F=3, B=4, D=5, E=6

Can anyone please suggest an efficient algorithm to achieve this?

Regards,

Anubrato

posted 4 years ago

What do you mean by 'efficient'? Efficient in terms of speed, memory, writing the code, understanding the code 3 months from now, or something else?

off the top of my head, I'd build the tree, populate it with the sequence, and then check each node to see if it is either a) the root node or b) it's parent has a lower sequence.\

or, start at the root, check to make sure each child has a HIGHER sequence, then recursively check its children.

off the top of my head, I'd build the tree, populate it with the sequence, and then check each node to see if it is either a) the root node or b) it's parent has a lower sequence.\

or, start at the root, check to make sure each child has a HIGHER sequence, then recursively check its children.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors