I am working on a simple program for homework on Hackerrank that plays with binary trees and displays them in post order, preorder, and in order along with other functionalities. Here is a sample run:
15
9
append 10
append 50
isBST
preOrder
append 45
height
levelOrder
deleteLastNode
postOrder
Correct Output:
true
15 10 50
2
15 10 50 45
10 50 15
2nd part: The first line (= 15 in the example) indicates that you have to build a binary tree with a root value 15. The second line (= 9 in the example) indicates the number of commands you have to conduct to the binary tree. The commands include “append” (= add a new number at the end of the tree), “isBST” (= checking if the binary tree is a binary search tree or not), “preOrder”, “height”, “levelOrder” (= visit the tree level-by-level from the root), “deleteLastNode”, and “postOrder”.
From what I understood when my teacher explained it: the append function is merely just level-order inserting of nodes into the tree. Height command is just the levels or depth of the tree (0 is just the root and -1 is no tree at all). and deleteLastNode is the node that is last appended into a tree, which I use a stack to keep track of the order of the inserted nodes. The order functions just display the tree in post-order, in-order, etc.
Now I am passing almost all of my test cases on the Hackerrank assignment except 2 hidden ones which result in segmentation faults. One test case that I tried was if you had to delete the root node first, and then, append another node/number but that didn't seem to be the case causing the segmentation fault. I then tried a case where you would run the deleteLastNode function when there are no more nodes but that did not seem to be the case that causes the segmentation fault. I am guessing that the segmentation faults have something to do with the deleteLastNode function but I might be wrong and I can't seem to think of another test case that does cause the fault. I am asking for what other possible test cases should I be aware of that can possibly cause the segmentation fault?
In case you need to see it, here is my code:
#include <iostream>
#include<string>
#include <climits>
#include <queue>
#include <string>
#include <stack>
using namespace std;
//struct and node stuff from Dr. Byun
struct Node
{
// Data part for a node.
int data;
Node* left;
Node* right;
// Constructor for a new node.
Node(int d)
{
data = d;
left = nullptr;
right = nullptr;
}
};
Node* mkTree(int data, Node* left, Node* right)
{
Node* root = new Node(data);
root->left = left;
root->right = right;
return root;
}
void inorder(Node* root)
{
if (root) // Or simply "if (root)"
{
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void preOrder(Node* root){
if (root){
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(Node* root){
if(root){
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
}
//source: https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = new Node(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = new Node(key);
break;
} else
q.push(temp->right);
}
}
//source: https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
int isBSTUtil(Node* node, int min, int max)
{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates
the min/max constraint */
if (node->data < min || node->data > max)
return 0;
/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}
void isBST(Node* node)
{
if(isBSTUtil(node, INT_MIN, INT_MAX) == 0){
cout << "false" << endl;
} else{
cout << "true" << endl;
}
}
//source: https://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/
int height(Node* root)
{
if (!root)
return -1;
else
{
/* compute the depth of each subtree */
int lDepth = height(root->left);
int rDepth = height(root->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth + 1);
else
return(rDepth + 1);
}
}
//source: https://www.geeksforgeeks.org/level-order-tree-traversal/
void printGivenLevel(Node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
void levelOrder(Node* root)
{
int h = height(root) + 1;
int i;
for (i = 1; i <= h; i++)
printGivenLevel(root, i);
}
//source: https://www.geeksforgeeks.org/deletion-binary-tree/
void deleteUtil(struct Node* root,
struct Node* d_node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}
Node* deletion(struct Node* root, int key)
{
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->data == key)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == key)
key_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
if (key_node != NULL) {
int x = temp->data;
deleteUtil(root, temp);
key_node->data= x;
}
return root;
}
// A sample main to create a binary tree like below.
// 5
// / \
// 3 4
// / \
// 1 2
//
int main()
{
// Node* n1 = new Node(1);
// Node* n2 = new Node(2);
// Node* n3 = mkTree(3, n1, n2);
// Node* n4 = new Node(4);
// Node* n5 = mkTree(5, n3, n4);
//inorder(n5);
//preOrder(n5);
//append(10, n5);
//deletion(n5, 2);
//inorder(n5);
// cout << height(n5);
int start_node;
int loop;
cin >> start_node;
cin >> loop;
Node* n1 = new Node(start_node);
stack<int> s;
s.push(start_node);
//cout << s.top() << endl;
for(int i = 0; i < loop; i++){
string command = "";
cin >> command;
//cout << "Loop number " << i + 1 << " and the command is " << command << endl;
if(command == "append"){
//cout << "reached\n";
if(!s.empty()){
int tempNum;
cin >> tempNum;
s.push(tempNum);
insert(n1, tempNum);
//cout << "Still here?\n";
}else{
int tempNum;
cin >> tempNum;
s.push(tempNum);
n1 = new Node(tempNum);
}
}else if(command == "isBST"){
isBST(n1);
}else if(command == "preOrder"){
preOrder(n1);
cout << endl;
}else if(command == "postOrder"){
postOrder(n1);
cout << endl;
}else if(command == "height"){
cout << height(n1) << endl;
}else if(command == "deleteLastNode"){
//cout << "Is stack empty?: " << s.empty() << endl;
if(s.empty()){
continue;
}else{
int selectedNode = s.top();
n1 = deletion(n1, selectedNode);
//cout << "Tree by lvlorder\n";
//levelOrder(n1); cout << endl;
s.pop();
//cout << "Is stack empty?: " << s.empty() << endl;
}
}else if(command == "levelOrder"){
levelOrder(n1);
cout << endl;
}else if(command == "inOrder"){
inorder(n1);
cout << endl;
}
}
// cout << "Current height: " << height(n1) << endl;
// inorder(n1);
return 0;
}
/**
other sample inputs:
50
7
height
append 5
height
deleteLastNode
height
deleteLastNode
height
30
14
isBST
append 10
append 50
append 5
append 20
append 40
append 70
isBST
append 80
isBST
deleteLastNode
deleteLastNode
isBST
levelOrder
15
9
append 10
append 50
isBST
preOrder
append 45
height
levelOrder
deleteLastNode
postOrder
30
5
deleteLastNode
height
append 10
height
inOrder
40
4
deleteLastNode
deleteLastNode
deleteLastNode
deleteLastNode
30
5
deleteLastNode
deleteLastNode
deleteLastNode
append 12
inOrder
40
5
append 40
append 40
append 40
append 40
inOrder
20
6
deleteLastNode
append 10
append 8
append 30
isBST
inOrder
**/
I apologize if this is not the right place to ask for help on a homework question.
Aucun commentaire:
Enregistrer un commentaire