My C++ exercise is about printing leave parent nodes in a binary tree. I've worked on two ideas to accomplish that. They are the following
/* Write a program that finds and prints all vertices of a binary tree which have
* successor leaves only */
#include <iostream>
class Node{
public:
int data;
Node* left = nullptr;
Node* right = nullptr;
Node(int value){data=value;}
};
bool traverse(Node* node);
bool traverse(Node* node){
if(!node->left&&!node->right)
return true;
if (traverse(node->left)||traverse(node->right))
std::cout<<node->data<<'\t';
if(node->left)
traverse(node->left);
if (node->right)
traverse(node->right);
}//Non-void function does not return a value in all control paths
Pros:
What I like about it is that I don't need to add any variables extra variables to it. That is a huge advantage if I want to use that method or a similar implementation in another tree because Node class is clean.
Cons
My main issue with my traverse function is that I don't now how to implement the missing return false; statement the compiler complains about. If I do that, there's not gonna be recursion in my understanding.
/* Write a program that finds and prints all vertices of a binary tree which have
* successor leaves only */
#include <iostream>
class Node{
public:
int data;
Node* left = nullptr;
Node* right = nullptr;
bool isLeaf = false;
Node(int value){data=value;}
};
void traverse(Node* node);
void traverse(Node* node){
if(!node->left&&!node->right){
node->isLeaf = true;
return;
}
if (node->left||node->right)
std::cout<<node->data<<'\t';
if(node->left)
traverse(node->left);
if (node->right)
traverse(node->right);
}
Pros:
I feel idea 2 is more effective and less adventurous in some way.
Cons
What I don't like about it is that it's got an extra variable that perhaps is not very useful if I put it into a more comprehensive tree class. To put it simpler, idea 2 looks less clean than 1
Bug
There's something about these two ideas that I can't figure out. Why don't they loop recursively? There's a return statement in both that avoids an infinite loop and the recursive calls happen as long as either right or left children exit. Can anyone let me know what I'm doing wrong with my traverse function please?
Question
I'd also like to make idea 1 work because I like the way it checks if a node is a parent of a leaf node by calling itself. How can I deal with the missing return false; statement the compiler wants me to include?
Edit
Just want to add the main function I created for them so you guys can see how I built the tree.
int main(){
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node (5);
root->right->left = new Node(6);
root->right->right = new Node(7);
traverse(root);
return 0;
}
My code isn't far from the solution as RandomBits told me. He/She pointed out some flaws in it and I tested it in a sandbox. The result is good but it prints leaf parents each time the function is called, something I don't understand now.
Took some time but I did it. Quite happy with the result, learned a lot from doing this exercise
/* Write a program that finds and prints all vertices of a binary tree which have
* successor leaves only */
#include <iostream>
class Node{
public:
int data;
Node* left = nullptr;
Node* right = nullptr;
Node(int value){data=value;}
};
bool isLeaf(Node* node){
return !node->left&&!node->right;
}
bool isParent(Node* node){
if(node)
return (isLeaf(node->left)||isLeaf(node->right));
else
return false;
}
void printParent(Node* node){
if(node == nullptr)
return;
if(!isLeaf(node)&&isParent(node))
std::cout<<node->data<<'\n';
if (node->left)
printParent(node->left);
if (node->right)
printParent(node->right);
}
int main(){
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->left->right = new Node(10);
root->left->left->left = new Node(11);
root->left->right = new Node (5);
root->right->left = new Node(6);
root->right->right = new Node(7);
printParent(root);
return 0;
}