Find the deepest path from root to its leaf node.
2. Data Structure and Algorithm
Recursive implementation pseudo-code:
- Get the deepest path of the path of the left child
- Get the deepest path of the path of the right child
- Return the deepest path of the left child if it is longer than the right
* Return the deepest path of the right child if it is longer than the left
- Special case: Return null path if this node is empty
Loop implementation pseudo-code:
- Generate a stack map
* In the order of each level
* Each level is separated by a NULL pointer
* Start from the root until the leaf nodes of the lowest level
- Take the stack map from backwards
* Take the first node of the lowest level (one of deepest path), Pn
* Populate out node of each level (use separator of NULL pointer)
* Find the parent of Pn -- Pn-1
* Loop the stack map until the root
3. C++ Implementation
Find the TreeNode definition, utility functions here: BST - Find Next In-Order Value and BTS - Print the First and Last Nodes of Each Level.
// Implementation
// ********************************************************************************
// Recursive implementation
template <typename T>
std::list<TreeNode<T>*> FindTheDeepestPath_R(TreeNode<T> *root)
{
if (!root) {
return std::list<TreeNode<T>*>();
}
// left path
std::list<TreeNode<T>*> leftPath = FindTheDeepestPath_R(root->left);
leftPath.emplace_front(root);
// right path
std::list<TreeNode<T>*> rightPath = FindTheDeepestPath_R(root->right);
rightPath.emplace_front(root);
return leftPath.size() >= rightPath.size() ? leftPath : rightPath;
}
// Loop implementation
template <typename T>
std::list<TreeNode<T>*> FindTheDeepestPath(TreeNode<T> *root)
{
if (!root) {
return std::list<TreeNode<T>*>();
}
std::stack<TreeNode<T>*> nodesInLevel;
std::queue<TreeNode<T>*> searchQueue;
searchQueue.push(root);
searchQueue.push(NULL);
TreeNode<T> * curNode = NULL; // empty node as separater
while (!searchQueue.empty()) {
curNode = searchQueue.front();
searchQueue.pop();
if (curNode) {
if (curNode->left) {
searchQueue.push(curNode->left);
}
if (curNode->right) {
searchQueue.push(curNode->right);
}
}
else if (!searchQueue.empty()) {
searchQueue.push(curNode);
}
nodesInLevel.push(curNode);
}
// nodeInLevel should have all nodes
// each level is separated by empty nodes
// start with root and end with empty nodes
std::list<TreeNode<T>*> path;
std::list<TreeNode<T>*> nodesInSameLevel;
while (!nodesInLevel.empty()) {
curNode = nodesInLevel.top();
nodesInLevel.pop();
if (!curNode) {
// found a level
if (!nodesInSameLevel.empty()) {
if (path.empty()) {
// it might have multipile path
// take the first one avaialbel
path.push_back(*nodesInSameLevel.rbegin());
}
else {
auto itEnd = nodesInSameLevel.cend();
for (auto it = nodesInSameLevel.cbegin(); it != itEnd; ++it) {
if ((*it)->left == path.back() || (*it)->right == path.back()) {
// find its parent node
path.push_back(*it);
break;
}
}
}
}
nodesInSameLevel.clear();
}
else {
nodesInSameLevel.push_back(curNode);
}
}
path.push_back(curNode);
path.reverse();
return path;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindTheDeepestPath()
{
std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0};
TreeNode<double> *root = NULL;
auto path = FindTheDeepestPath(root);
assert(path.empty() == true);
path = FindTheDeepestPath_R(root);
assert(path.empty() == true);
// 3
// 1 4
// 2 5
root = ConstructTreeOnSortedValueBFS(input);
path = FindTheDeepestPath(root);
TestResult<double>(path, {3.0, 1.0, 2.0});
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 1.0, 2.0 });
input = { 6.0, 7.0, 8.0, 9.0 };
TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
input = { 10.0, 11.0, 12.0, 13.0 , 14.0};
TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
input = { 15.0, 16.0, 17.0, 18.0 };
TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
TreeNode<double> *subTree4 = ConstructTreeRecursive(input);
TreeNode<double> *leftestNode = FindLeftestNode(root);
assert(leftestNode != NULL);
leftestNode->left = subTree1;
// 3
// 1 4
// 8 2 5
// 6 9
// 7
path = FindTheDeepestPath(root);
TestResult<double>(path, { 3.0, 1.0, 8.0, 6.0, 7.0 });
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 1.0, 8.0, 6.0, 7.0 });
TreeNode<double> *rightestNode = FindRightestNode(root);
assert(rightestNode != NULL);
rightestNode->left = subTree2;
// 3
// 1 4
// 8 2 5
// 6 9 12
// 7 10 13
// 11 14
path = FindTheDeepestPath(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 10.0, 11.0 });
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 10.0, 11.0 });
TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
assert(firstLeftRighestNode != NULL);
firstLeftRighestNode->right = subTree3;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
path = FindTheDeepestPath(root);
TestResult<double>(path, { 3.0, 1.0, 2.0, 17.0, 15.0, 16.0 });
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 1.0, 2.0, 17.0, 15.0, 16.0 });
TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
assert(firstRightLeftestNodeOfS2 != NULL);
firstRightLeftestNodeOfS2->left = subTree4;
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21
// 19 22
// 20 23
path = FindTheDeepestPath(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 10.0, 11.0, 21.0, 19.0, 20.0 });
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 10.0, 11.0, 21.0, 19.0, 20.0 });
TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
assert(rightestNodeOfS2 != NULL);
for (size_t i = 0; i < 8; ++i) {
rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
rightestNodeOfS2 = rightestNodeOfS2->right;
}
// 3
// 1 4
// 8 2 5
// 6 9 17 12
// 7 15 18 10 13
// 16 11 14
// 21 100
// 19 22 101
// 20 23 102
// 103
// 104
// 105
// 106
// 107
// clean up
path = FindTheDeepestPath(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0, 101.0,
102.0, 103.0, 104.0, 105.0, 106.0, 107.0 });
path = FindTheDeepestPath_R(root);
TestResult<double>(path, { 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0, 101.0,
102.0, 103.0, 104.0, 105.0, 106.0, 107.0 });
// clean up
DeleteTree_TD(&root);
}
No comments:
Post a Comment