This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,
"
Print first and last node of all the levels of a tree.
Ex if tree is -
root->data = 1
root->left->data = 2
root->right->data = 3
root->left->right->data = 4
root->right->right->data = 6
root->right->left->data = 5
root->right->left->left->data = 7
root->right->left->left->right->data = 8
Output - 1 2 3 4 6 7 8
- neer.1304 9 days ago in United States root->data = 1
root->left->data = 2
root->right->data = 3
root->left->right->data = 4
root->right->right->data = 6
root->right->left->data = 5
root->right->left->left->data = 7
root->right->left->left->right->data = 8
Output - 1 2 3 4 6 7 8
2.Analysis
Naturally it is common to think of using breadth-first search to find out all the nodes in each level and print the the first and the last node of this level.
There is one edge case that the level has only one node, and this means that the only node is the first and the last node at the same time. In this case just avoid to print it twice.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <cassert>
#include <memory>
#include <queue>
#include <stack>
#include <vector>
template<typename T>
struct TreeNode
{
TreeNode(const T& d)
: data(new T(d)), left(nullptr), right(nullptr)
{}
~TreeNode()
{
std::shared_ptr<T>().swap(data);
}
std::shared_ptr<T> data;
TreeNode* left;
TreeNode* right;
};
template<typename T>
struct TreeConstructionBFS
{
TreeConstructionBFS()
{}
TreeConstructionBFS(TreeNode<T>* p, bool left, int s, int e)
: parent(p), isLeftChild(left), start(s), end(e)
{}
TreeNode<T>* parent = nullptr;
bool isLeftChild = false;
int start = 0;
int end = -1;
};
template<typename T>
TreeNode<T>* ConstructTreeOnSortedValueBFS(const std::vector<T>& input)
{
if (input.empty()) {
return nullptr;
}
const int len = input.size();
int index = len >> 1;
TreeNode<T>* root = new TreeNode<T>(input[index]);
std::queue<TreeConstructionBFS<T>> nodesToBuild;
nodesToBuild.push(TreeConstructionBFS<T>(root, true, 0, index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(root, false, index + 1, len - 1));
while (!nodesToBuild.empty()) {
const TreeConstructionBFS<T>& curCon = nodesToBuild.front();
if (curCon.start > curCon.end) {
if (curCon.isLeftChild) {
curCon.parent->left = nullptr;
}
else {
curCon.parent->right = nullptr;
}
}
else {
index = (curCon.start + curCon.end) >> 1;
TreeNode<T>* tempNode = new TreeNode<T>(input[index]);
if (curCon.isLeftChild) {
curCon.parent->left = tempNode;
}
else {
curCon.parent->right = tempNode;
}
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
true,
curCon.start,
index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
false,
index + 1,
curCon.end));
}
nodesToBuild.pop();
}
return root;
}
template<typename T>
void GetFirstAndLastOfEachLevelOfTree(TreeNode<T>* root,
std::vector<TreeNode<T>*>& listOfFL)
{
if (root == nullptr) {
return;
}
std::queue<TreeNode<T>*> nodes;
nodes.push(root);
nodes.push(nullptr); // dummy node as separator of levels
TreeNode<T>* first;
TreeNode<T>* prev = nullptr;
while (!nodes.empty()) {
TreeNode<T>* curNode = nodes.front();
nodes.pop();
if (curNode == nullptr) {
listOfFL.push_back(first);
// here if equal, then this is an edge case
if (prev != first) {
listOfFL.push_back(prev);
}
if (nodes.empty()) {
break;
}
nodes.push(nullptr); // dummy node as separator of levels
}
else {
if (prev == nullptr) {
// dummy node as separator and start of new level
first = curNode;
}
if (curNode->left != nullptr) {
nodes.push(curNode->left);
}
if (curNode->right != nullptr) {
nodes.push(curNode->right);
}
}
prev = curNode;
}
}
// Test
// ********************************************************************************
void TestCasesOfFirstAndLastOfEachLevelOfTree()
{
std::vector<int> testInput{ 1 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
std::vector<TreeNode<int>*> result;
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 1);
assert(*result[0]->data == 1);
DeleteTree(&rootBFS);
testInput = { 1, 2 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(*result[0]->data == 2);
assert(*result[1]->data == 1);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 3);
assert(*result[0]->data == 2);
assert(*result[1]->data == 1);
assert(*result[2]->data == 3);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 7);
// Tree:
// 6
// 3, 8
// 1, 4, 7, 9
// 2, 5, 10
assert(*result[0]->data == 6);
assert(*result[1]->data == 3);
assert(*result[2]->data == 8);
assert(*result[3]->data == 1);
assert(*result[4]->data == 9);
assert(*result[5]->data == 2);
assert(*result[6]->data == 10);
DeleteTree(&rootBFS);
}
No comments:
Post a Comment