Skip to content

Instantly share code, notes, and snippets.

@jameshi16
Created June 18, 2019 13:54
Show Gist options
  • Save jameshi16/8b2a6483ae2d304070fd35f5b4004ad1 to your computer and use it in GitHub Desktop.
Save jameshi16/8b2a6483ae2d304070fd35f5b4004ad1 to your computer and use it in GitHub Desktop.
[Mine] Binary Tree Traversal
#include <iostream>
//==RELATED TO INTERVIEW==
//Q: Return next element (if 9, return 11), -2 if next element doesn't exist, -1 if element itself doesn't exist
struct Node {
Node *left = nullptr;
Node *parent = nullptr;
Node *right = nullptr;
int value = 0;
};
int sorted[8];
int sorted_it = 0;
void traverse(Node* parent_node) {
if (parent_node->left != nullptr)
traverse(parent_node->left);
*(sorted + sorted_it++) = parent_node->value;
if (parent_node->right != nullptr)
traverse(parent_node->right);
}
int binarySearchNext(int* list, int list_size, int element) {
int *start = list, *end = list + list_size -1;
int* it;
if (*end == element) //next element cannot exist
return -2;
while (true) {
it = start + (end - start) / 2; //get middle everytime
if (*it == element) {
it++;
break;
}
if (*it < element)
start = it;
if (*it > element)
end = it;
if (it == start)
return -1; //can't even find the element
}
return *it;
}
//===NOT RELATED TO INTERVIEW===
void insert(Node* parent_node, int val) {
if (val < parent_node->value) { //less
if (parent_node->left == nullptr)
parent_node->left = new Node{nullptr, nullptr, nullptr, val};
else insert(parent_node->left, val);
}
if (val > parent_node->value) { //more
if (parent_node->right == nullptr)
parent_node->right = new Node{nullptr, nullptr, nullptr, val};
else insert(parent_node->right, val);
}
}
int main() {
//create tree
int numbers[] = {15, 10, 9, 11, 20, 19, 23, 25};
Node *parent_node = new Node{nullptr, nullptr, nullptr, numbers[0]};
for (int i = 1; i < 8; i++)
insert(parent_node, numbers[i]);
traverse(parent_node);
std::cout << binarySearchNext(sorted, 8, 11) << std::endl;
return 0;
}
#include <iostream>
//==RELATED TO INTERVIEW==
//Q: Return next element (if 9, return 11), -2 if next element doesn't exist, -1 if element itself doesn't exist
struct Node {
Node *left = nullptr;
Node *parent = nullptr;
Node *right = nullptr;
int value = 0;
};
bool element_found = false;
Node* nextElementNode = nullptr; //answer will be here
void traverse(Node* parent_node, int num) {
if (parent_node->left != nullptr)
traverse(parent_node->left, num);
if (element_found)
if (nextElementNode == nullptr)
nextElementNode = parent_node;
else return;
if (num == parent_node->value)
element_found = true;
if (parent_node->right != nullptr)
traverse(parent_node->right, num);
}
int findNextElement(Node* parent_node, int num) {
traverse(parent_node, num);
if (element_found && nextElementNode == nullptr)
return -2;
if (!element_found && nextElementNode == nullptr)
return -1;
return nextElementNode->value;
}
//===NOT RELATED TO INTERVIEW===
void insert(Node* parent_node, int val) {
if (val < parent_node->value) { //less
if (parent_node->left == nullptr)
parent_node->left = new Node{nullptr, nullptr, nullptr, val};
else insert(parent_node->left, val);
}
if (val > parent_node->value) { //more
if (parent_node->right == nullptr)
parent_node->right = new Node{nullptr, nullptr, nullptr, val};
else insert(parent_node->right, val);
}
}
int main() {
//create tree
int numbers[] = {15, 10, 9, 11, 20, 19, 23, 25};
Node *parent_node = new Node{nullptr, nullptr, nullptr, numbers[0]};
for (int i = 1; i < 8; i++)
insert(parent_node, numbers[i]);
std::cout << findNextElement(parent_node, 11) << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment