Binary Tree Recursion Problem
-
Does somebody have an idea why will the following happen: printf("Min Value: %d\n", minValue(root)); printf("Max Value: %d\n", maxValue(root)); // not sure why line below throws segmentation core //printf("Min Val: %d Max Val: %d\n", minValue(root), maxValue(root)); minValue and maxValue are recursive functions returning the min/max value of a binary tree, when called separately as in lines 1 & 2 they work fine, but when called from the same printf statement I get a segmenation fault in linux. Thanks!
-
Does somebody have an idea why will the following happen: printf("Min Value: %d\n", minValue(root)); printf("Max Value: %d\n", maxValue(root)); // not sure why line below throws segmentation core //printf("Min Val: %d Max Val: %d\n", minValue(root), maxValue(root)); minValue and maxValue are recursive functions returning the min/max value of a binary tree, when called separately as in lines 1 & 2 they work fine, but when called from the same printf statement I get a segmenation fault in linux. Thanks!
Without seeing how
minValue()and/ormaxValue()are implemented, it'd simply be a guess. Perhaps the functions are not "unwinding" correctly."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
Without seeing how
minValue()and/ormaxValue()are implemented, it'd simply be a guess. Perhaps the functions are not "unwinding" correctly."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
I will paste the code. But they are working fine when they are called individually.
int minValue(TreeNode * root) {
TreeNode * current = root;
if (current == NULL) return -1;
else {
while (current->left != NULL)
current = current->left;
return current->num;
}
}int maxValue(TreeNode * root) {
TreeNode * current = root;
if (current == NULL)
return -1;
else
{
while (current->right != NULL)
current = current->right;
return current->num;
}
}And they are called as posted above. One more time, when called individually they work fine.
-
I will paste the code. But they are working fine when they are called individually.
int minValue(TreeNode * root) {
TreeNode * current = root;
if (current == NULL) return -1;
else {
while (current->left != NULL)
current = current->left;
return current->num;
}
}int maxValue(TreeNode * root) {
TreeNode * current = root;
if (current == NULL)
return -1;
else
{
while (current->right != NULL)
current = current->right;
return current->num;
}
}And they are called as posted above. One more time, when called individually they work fine.
Where's the recursion?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
Where's the recursion?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
I'm sorry, the recursion is in other functions, not in this one. Do you know why it's not working when they are called together?
-
I'm sorry, the recursion is in other functions, not in this one. Do you know why it's not working when they are called together?
Just a theory, but does the following work:
int min = minValue(root)
int max = maxValue(root));
printf("Min Val: %d Max Val: %d\n", min, max);"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
Just a theory, but does the following work:
int min = minValue(root)
int max = maxValue(root));
printf("Min Val: %d Max Val: %d\n", min, max);"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
That works, but I wanted to understand why the other version does not work? Here is all the code if you want to try.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct treenode {
int num;
struct treenode * left;
struct treenode * right;
} TreeNode;int recLookup (TreeNode *, int);
int lookUp(TreeNode *, int);
int sizeRec(TreeNode *);
int maxDepth(TreeNode *);
int minValue(TreeNode *);
int maxValue(TreeNode *);
int hasPathSum(TreeNode *, int);TreeNode * createNode (int);
TreeNode * insertRec(TreeNode *, int);
TreeNode * buildTree();void deleteRec(TreeNode *);
void printIncreasing(TreeNode *);
void printPostOrder(TreeNode *);
void printPaths(TreeNode *);
void printPathRecur(TreeNode *, int[], int);enum { FALSE, TRUE };
int main (void) {
TreeNode * root = buildTree();
printf("Size: %d\n", sizeRec(root));
printf("Max Depth: %d\n", maxDepth(root));
printf("Min Value: %d\n", minValue(root));
printf("Max Value: %d\n", maxValue(root));
printIncreasing(root); puts("");
printPostOrder(root); puts("");
printf("Has path sum 15: %d\n", hasPathSum(root, 15));
printPaths(root);
// not sure why line below throws segmentation core
printf("Min Val: %d Max Val: %d\n", minValue(root), maxValue(root));deleteRec(root); return 0;}
void printPaths(TreeNode * root) {
int path[10];
int pathLen = 0;
printPathRecur(root, path, pathLen);
}void printPathRecur(TreeNode * node, int path[], int pathLen) {
if (node == NULL) return;
path[pathLen] = node->num;
pathLen++;
if (node->right == NULL && node->left == NULL) {
int i;
for (i = 0; i < pathLen; i++)
printf("%d ", path[i]);
puts("");
}
else {
printPathRecur(node->left, path, pathLen);
printPathRecur(node->right, path, pathLen);
}
}int hasPathSum(TreeNode * root, int num) {
TreeNode * current = root;
if (current == NULL)
return num == 0;
else {
int n = num - current->num;
return
hasPathSum(current->left, n) ||
hasPathSum(current->right, n);
}
}void printPostOrder(TreeNode * root) {
TreeNode * current = root;
if (current == NULL) return;
printPostOrder(current->left) -
That works, but I wanted to understand why the other version does not work? Here is all the code if you want to try.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct treenode {
int num;
struct treenode * left;
struct treenode * right;
} TreeNode;int recLookup (TreeNode *, int);
int lookUp(TreeNode *, int);
int sizeRec(TreeNode *);
int maxDepth(TreeNode *);
int minValue(TreeNode *);
int maxValue(TreeNode *);
int hasPathSum(TreeNode *, int);TreeNode * createNode (int);
TreeNode * insertRec(TreeNode *, int);
TreeNode * buildTree();void deleteRec(TreeNode *);
void printIncreasing(TreeNode *);
void printPostOrder(TreeNode *);
void printPaths(TreeNode *);
void printPathRecur(TreeNode *, int[], int);enum { FALSE, TRUE };
int main (void) {
TreeNode * root = buildTree();
printf("Size: %d\n", sizeRec(root));
printf("Max Depth: %d\n", maxDepth(root));
printf("Min Value: %d\n", minValue(root));
printf("Max Value: %d\n", maxValue(root));
printIncreasing(root); puts("");
printPostOrder(root); puts("");
printf("Has path sum 15: %d\n", hasPathSum(root, 15));
printPaths(root);
// not sure why line below throws segmentation core
printf("Min Val: %d Max Val: %d\n", minValue(root), maxValue(root));deleteRec(root); return 0;}
void printPaths(TreeNode * root) {
int path[10];
int pathLen = 0;
printPathRecur(root, path, pathLen);
}void printPathRecur(TreeNode * node, int path[], int pathLen) {
if (node == NULL) return;
path[pathLen] = node->num;
pathLen++;
if (node->right == NULL && node->left == NULL) {
int i;
for (i = 0; i < pathLen; i++)
printf("%d ", path[i]);
puts("");
}
else {
printPathRecur(node->left, path, pathLen);
printPathRecur(node->right, path, pathLen);
}
}int hasPathSum(TreeNode * root, int num) {
TreeNode * current = root;
if (current == NULL)
return num == 0;
else {
int n = num - current->num;
return
hasPathSum(current->left, n) ||
hasPathSum(current->right, n);
}
}void printPostOrder(TreeNode * root) {
TreeNode * current = root;
if (current == NULL) return;
printPostOrder(current->left)In
buildTree(), change the first statement to:TreeNode * root = insertRec(NULL, 4);
As you had it,
rootwas being used without having been initialized."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
In
buildTree(), change the first statement to:TreeNode * root = insertRec(NULL, 4);
As you had it,
rootwas being used without having been initialized."One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
You solved it, thanks!