Find the longest sequence in a binary tree
2. Data Structure and Algorithm
Pseudo-code:
- Generate the depth map for each node
* maximal depth of the left child
* maximal depth of the right child
- Go through then map and spot the node, Nx, with maximal sum of left and right depths
- Find the deepest path, Pl of the left child of Nx
- Find the deepest path, Pr of the right child of Nx
- Revert Pl and join Pl, Nx and Pr as the longest sequence
Find the deepest path check details: BTS - Find the Deepest Path
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
// ********************************************************************************
struct TreeNodeDepth{
TreeNodeDepth()
: depthOfLeft(0)
, depthOfRight(0)
{}
TreeNodeDepth(const size_t left, const size_t right)
: depthOfLeft(left)
, depthOfRight(right)
{}
size_t Total() const {
return depthOfLeft + depthOfRight;
}
// depth of left and right children
size_t depthOfLeft;
size_t depthOfRight;
};
template <typename T>
using DepthMap = std::unordered_map<TreeNode<T>*, TreeNodeDepth>;
template <typename T>
size_t GenerateDepthMap(TreeNode<T> *root, DepthMap<T> &depth) {
if (!root) {
// special case - NULL pointer
return 0;
}
// depth of this node and save into the map
size_t leftDepth = GenerateDepthMap(root->left, depth);
size_t rightDepth = GenerateDepthMap(root->right, depth);
depth.insert(std::make_pair(root, TreeNodeDepth(leftDepth, rightDepth)));
// return the maximal depth of left and right path
return leftDepth >= rightDepth ? (leftDepth + 1) : (rightDepth + 1);
}
template <typename T>
std::list<TreeNode<T>*> FindTheLongestSequence(TreeNode<T> *root)
{
if (!root) {
// special case - NULL pointer
return std::list<TreeNode<T>*>();
}
// Generate the depth map
DepthMap<T> depth;
GenerateDepthMap(root, depth);
size_t totalLength = 0;
TreeNode<T>* nodeWithTheLongestSeq = NULL;
auto itEnd = depth.rend();
// Loop through the depth map and find the longest sequence
// Spot the node with largest sum of depth of left and right children
for (auto it = depth.rbegin(); it != itEnd; ++it) {
if (it->second.Total() > totalLength) {
nodeWithTheLongestSeq = it->first;
totalLength = it->second.Total();
}
}
// Find the deepest path of the left child
std::list<TreeNode<T>*> leftBranchPath =
FindTheDeepestPath(nodeWithTheLongestSeq->left);
// Find the deepest path of the right child
std::list<TreeNode<T>*> rightBranchPath =
FindTheDeepestPath(nodeWithTheLongestSeq->right);
// Join them to form the sequence
leftBranchPath.reverse();
leftBranchPath.push_back(nodeWithTheLongestSeq);
leftBranchPath.splice(leftBranchPath.end(), rightBranchPath);
return leftBranchPath;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindTheLongestSeq()
{
std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
TreeNode<double> *root = NULL;
auto path = FindTheLongestSequence(root);
assert(path.empty() == true);
// 3
// 1 4
// 2 5
root = ConstructTreeOnSortedValueBFS(input);
path = FindTheLongestSequence(root);
TestResult<double>(path, { 2.0, 1.0, 3.0, 4.0, 5.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 = FindTheLongestSequence(root);
TestResult<double>(path, { 7.0, 6.0, 8.0, 1.0, 3.0, 4.0, 5.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 = FindTheLongestSequence(root);
TestResult<double>(path, { 7.0, 6.0, 8.0, 1.0, 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 = FindTheLongestSequence(root);
TestResult<double>(path, { 16.0, 15.0, 17.0, 2.0, 1.0, 3.0,
4.0, 5.0, 12.0, 10.0, 11.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 = FindTheLongestSequence(root);
TestResult<double>(path, { 16.0, 15.0, 17.0, 2.0, 1.0, 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;
}
TreeNode<double> *rightestNodeOfS4 = FindRightestNode(subTree4);
assert(rightestNodeOfS4 != NULL);
for (size_t i = 0; i < 4; ++i) {
rightestNodeOfS4->left = new TreeNode<double>(50.0 + i);
rightestNodeOfS4 = rightestNodeOfS4->left;
}
// 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
// 50 103
// 51 104
// 52 105
// 53 106
// 107
path = FindTheLongestSequence(root);
TestResult<double>(path, { 53.0, 52.0, 51.0, 50.0, 23.0, 22.0, 21.0,
11.0, 10.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