Alphabet Chain in Binary Tree

[calvinfornia]

Hi, I'm working on a project :

Given an alphabet binary tree, find the length of the longest vowel chain and the node IDs on that chain.
The length is defined as the number of edges in the chain.
For example, a chain with 4 nodes has a length of 3.
The longest chain has to meet the following rules :
1. Nodes in the chain can only include vowels.
2. Nodes in the chain can only go through once.
Node ID starts from 1. Child ID will be 0 if the child is NULL.
Alphabet must be lowercase. The node list is sorted bottom up, which means the node’s children ID must smaller than its.
The last node in the list is the tree root.

For example an input :

9

1 e 0 0
2 z 0 0
3 e 1 2
4 i 0 0
5 e 0 0
6 h 0 0
7 a 3 4
8 w 5 6
9 f 7 8

will get the output :

3 

1
3
7
4

This project is required to be done using the "Divide and Conquer" method and recursion. Still not having any idea for now.

Looking for some aid, a part of inspiring psuedocode will be great.
Thanks a lot in advance !

[ne555]

let's simplify the problem
say that all the nodes are vowels, ¿what will be the solution?

[dhayden]

I'm having trouble understanding how the binary tree is constructed. What do the input lines mean?

The node list is sorted bottom up, which means the node’s children ID must smaller than its.

This sounds more like a heap than a binary tree.

[calvinfornia]

In the output, there will be the length of the longest chain and the ID of nodes in the chain.
When printing the IDs, it starts from the endpoint whose ID is smaller.

[dhayden]

I think I understand the output. It's the input that confused me. Here's your example input:

9

1 e 0 0
2 z 0 0
3 e 1 2
4 i 0 0
5 e 0 0
6 h 0 0
7 a 3 4
8 w 5 6
9 f 7 8

It looks like the first line with "9" on it indicates that there are 9 more lines that follow.
And each of those lines specifies...a node? Each line has 4 characters. What do each of those characters mean?

[calvinfornia]

9

1 e 0 0
2 z 0 0
3 e 1 2
4 i 0 0
5 e 0 0
6 h 0 0
7 a 3 4
8 w 5 6
9 f 7 8

The first number stands for the number of nodes in the tree(eg 9)
And there are following 9 lines, each for a node.
In every line,
First number is the node's No.
Second character is the alphabet it stores in the node.
Third number is the node's No. of its left children.
Forth number is the node's No. of its right children.

Thx!

[jonnin]

heh, you don't need a tree, the file tells you, and I believe you can solve it directly from the file input PDQ. 731 perhaps? aee? Parse the file, unravel the strings created by the chains using the left/right info, and then examine the strings...

hmm.
if I had to do it with D&C I would see if there is a way to find the roots of subtrees and
load up from there, adding only vowels to each tree.
then process each tree in its own thread and the longest wins?

that may be overthinking it.
if you just load 1 tree, you can call your search for chains on each consonant node and traverse the entire tree node by node doing that. the longest one wins. Simpler, but does much more work.

can you find a smart early exit (is there a way to find the longest one as the first one you find? It seems like 'maybe')

[dhayden]

Thanks for the description. Oddly, this is the second question in 2 days where a binary tree was specified with the node numbers. Go figure.

Anyway, given the root of the longest path, there are two possibilities:
1. the path starts at the root and runs down through a bunch of descendents, or
2. the path starts down the left tree, runs up through the root, and then goes down the right tree.

My solution is more complicated than I thought it would be. Perhaps there's an easier way. I distinguished between a string of vowels, which is a string that starts at a node and runs through the descendents, and a chain of vowels, which can be a string, or, if both children are vowels, then the it starts down one child, runs up through the current node, and then down the other. So a string is case 1 and a chain is case 2.

Each node stores the length of the longest string rooted at that node. I stored the nodes in a vector and the left and right "pointers" are really indices into the vector

struct Node {
    char ch = 0;
    // index into nodes of the left & right trees. zero means none
    unsigned left=0, right=0;

    // length of the longest string of vowels starting with this node
    // and running down through the descendents.
    unsigned length=0;
};
vector<Node> nodes;

A helper function computes the length of the longest chain in a subtree that also runs through the subtree's root:

unsigned longestChain(unsigned idx)
{
    if (idx == 0) return 0;

    Node &node(nodes[idx]);

    if (!isVowel(node.ch)) {
        return 0;
    }
    unsigned rightLen = (node.right ? nodes[node.right].length : 0U);
    unsigned leftLen = (node.left   ? nodes[node.left].length : 0U);
    unsigned result = 1 + rightLen+leftLen;
    return result;
}

You could store that length too I suppose but it seemed easy to compute.

Finally, there's the recursive function. It needs to do a lot:
- Call itself on its children
- set the length of the longest string rooted at this node.
- compute the length of the longest chain through this node.
- return the index of the node that contains the longest chain in the subtree.

I stored length as the number of nodes in a string or chain, not the number of edges. That way a node with a vowel and no children has a chain length of 1, which a node iwth a non-vowel has a chain length of 0.

When the recursive function returns the index of the root of the longest chain, you have to print it:
- recursively print the longest string of the left child
- print the node's index
- recursively print the longest string of the right child.