Vowel chain in binary tree

calvinfornia (48)
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.
3. The chain can start from the left sub-tree to the root and to the right sub-tree.
Node ID starts from 1. Child ID will be 0 if the child is NULL.
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.

Here's my code so far for only the chain length part. But there's a problem, which is after running it, it returns an extremely large number, and also empty in the output file.
How can the problem be solved?
Thx a lot in advance!!

Below is the case1.txt :
9
0

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(ie 9)
And there are following 9 lines, each for a node.
In every line,
First number is the node's ID.
Second character is the alphabet it stores in the node.
Third number is the node's ID of its left children.
Forth number is the node's ID of its right children.

And here's the source code, the algorithm of computing the longest length has been proved to be correct :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
// C++ program to find the length of longest 
// path with same values in a binary tree. 
#include <bits/stdc++.h> 
using namespace std; 
  

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
	int ID;
	char val; 
	struct Node *left, *right; 
}; 
  
  
/* Function to print the longest path 
   of same values */
int length(Node *node, int *ans) 
{ 
	if (node == NULL)
	{ 
		return 0; 
	}
  
	// Recursive calls to check for subtrees 
	int left = length(node->left, ans); 
	int right = length(node->right, ans); 
  
	// Variables to store maximum lengths in two directions 
	int Leftmax = 0, Rightmax = 0; 
  
	// If curr node and it's left child are all vowels 
	if ((node->left) && (node->left->val == 'a' || node->left->val == 'e' || node->left->val == 'i' || node->left->val == 'o' || node->left->val == 'u') && 
	   (node->val == 'a' || node->val == 'e' || node->val == 'i' || node->val == 'o' || node->val == 'u'))  
	{
		Leftmax += left + 1;
	}
  
	// If curr node and it's right child are all vowels
	if ((node->right) && (node->right->val == 'a' || node->right->val == 'e' || node->right->val == 'i' || node->right->val == 'o' || node->right->val == 'u') && 
	   (node->val == 'a' || node->val == 'e' || node->val == 'i' || node->val == 'o' || node->val == 'u'))  
    {
		Rightmax += right + 1; 
	}
	
	*ans = max(*ans, Leftmax + Rightmax); 
	return max(Leftmax, Rightmax); 
} 
  
  
/* Driver function to find length of 
   longest same value path*/
int longestSameValuePath(Node *root) 
{ 
	int ans = 0; 
	length(root, &ans); 
	return ans; 
} 
  
  
/* Helper function that allocates a 
new node with the given data and 
NULL left and right pointers. */
Node *newNode(char data) 
{ 
	Node *temp = new Node; 
	temp->val = data; 
	temp->left = temp->right = NULL; 
	return temp; 
} 
  

int main() 
{ 
	/* Let us construct a Binary Tree 
          a 
         / \ 
        a   a 
       / \ / \ 
      a  a b  b 
   	 / \
	a   b
	
	Node *root = NULL; 
	root = newNode('a'); 
	root->left = newNode('a');
	root->left->left = newNode('a'); 
	root->left->left->left = newNode('a');  
	root->left->left->right = newNode('b'); 
	root->left->right = newNode('a'); 
 
	root->right = newNode('a'); 
	root->right->left = newNode('b'); 
	root->right->right = newNode('b'); 
	*/
  
	ifstream fin("case1.txt") ;
	if(!fin)
	{
		cout << "\nError in open case data.txt\n" ;
		return -1 ;
	}
	
	ofstream fout ;
	fout.open("case1_result.txt");
	
	
	int node_num, mode_no;
	int node_ID, left_ID, right_ID;
	char data;
	while(fin >> node_num)
	{
		fin >> mode_no;
		Node* nodes[node_num];
		
		for(int i=1; i <= node_num; i++)
		{
			fin >> node_ID >> data >> left_ID >> right_ID;
			nodes[i]->ID  = node_ID;
			nodes[i]->val = data;
			nodes[i]->left = nodes[left_ID];
			nodes[i]->right = nodes[right_ID];
		}
		Node *root = NULL; 
		root = nodes[node_num]; 
		cout << longestSameValuePath(root); 
		fout << longestSameValuePath(root); 
	}
	
	fout.close();
	return 0; 
}
Last edited on
ne555 (10692)
for(int i=1; i <= node_num; i++)
valid array indices goes from 0 to size-1, not from 0 to size

Node* nodes[node_num];
all those pointers are invalid

// If curr node and it's left child has same value
the code doesn't reflect the comment
calvinfornia (48)
Sorry, can you explain in more detail?
Why are all these pointers invalid?

Oh, the comment should be removed. I forgot it.
Thx for reminding, I've fixed it.

That's what I get after executing:

--------------------------------
Process exited after 4.369 seconds with return value 3221225477
Last edited on
ne555 (10692)
awesome, your program crashes and you didn't even notice.
run your program through a debugger

> Why are all these pointers invalid?
because they are uninitialised, they do not point to a valid Node object
actually, there isn't a single Node object in your program.
Topic archived. No new replies allowed.