# Tree problems part 2

## 236. LCA

• Thought:
• (1) Store the information of the parent node of each node.
• (2) Ascend the node if the node is deeper in order to get closer to the common parent, finally the lowest common ancestor will match . It is quite intuitive. You may imagine by drawing a picture.
• The rest of the explanations are written in the comment part of the code
• Analysis: Time complexity O(N), Space complexity O(N)
class Solution
{
public:
struct node_info
{
TreeNode* parent;
int depth;
};
map<TreeNode*, node_info> node_info_map;
TreeNode* res;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* node_p, TreeNode* node_q)
{
dfs_information(root, 0);
node_info_map[root].parent = root; // for the root itself, preventing runtime error
res = root; // initialize
climbup_LCA(node_p, node_q); // solve
return res;
}

// step1, traverse the tree first to find the child-parent pair
void dfs_information(TreeNode* root, int depth)
{
if(root == NULL)
{
return;
}
node_info_map[root].depth = depth;
if(root->left) // Store the child-parent information for left child node if it is a non-null one
{
node_info_map[root->left].parent = root;
dfs_information(root->left, depth + 1);
}
if(root->right) // Store the child-parent information for right child node if it is a non-null one
{
node_info_map[root->right].parent = root;
dfs_information(root->right, depth + 1);
}
}

// step2, climb up to find the LCA, using depth comparison algorithm
void climbup_LCA(TreeNode* node_p, TreeNode* node_q)
{
if(node_info_map[node_p].parent == node_info_map[node_q].parent)
{
res = node_info_map[node_p].parent;
return;
}
else if(node_info_map[node_p].parent == node_q)
{
res = node_q;
return;
}
else if(node_info_map[node_q].parent == node_p)
{
res = node_p;
return;
}

// the deeper node has to climb up one depth
else if(node_info_map[node_p].depth > node_info_map[node_q].depth)
{
climbup_LCA(node_info_map[node_p].parent, node_q);
}
else
{
climbup_LCA(node_p, node_info_map[node_q].parent);
}
}
};


## 863. All Nodes Distance K in Binary Tree

• Thought:
• (1) Store the information of the parent node of each node.
• (2) Starting from the target node, traverse the parent node, left child, right child. Remember to mark the node visited, consequently it will prevent child -> parent and parent -> child, two times back and forth resulting in an 0 distance just owing to 2 - 1(child -> parent) - 1(parent -> child), but it is not the case of answer.
• Analysis: Time complexity O(N), Space complexity O(N)
// 12ms
class Solution
{
public:
unordered_map<TreeNode*, TreeNode*> parent_map;
vector<int> res;
vector<int> distanceK(TreeNode* root, TreeNode* target, int K)
{
dfs_parent(root);
dist(target, K);
return res;
}
void dfs_parent(TreeNode* root)
{

if(root -> left) // store the child-parent information for the left child node
{
parent_map[root -> left] = root;
dfs_parent(root -> left);
}

if(root -> right) // store the child-parent information for the right child node
{
parent_map[root -> right] = root;
dfs_parent(root -> right);
}
}
void dist(TreeNode* target, int K)
{
if(target -> val < 0)// do not push_back too much redundant node
{
return;
}

if(K == 0)
{
res.push_back(target -> val);
return; //exit immediately to prevent stackoverflow
}

target -> val = -1; // mark as done

if(parent_map.count(target)) // check for parent
{
dist(parent_map[target], K - 1);
}

if(target -> left)
{
dist(target -> left, K - 1);
}

if(target -> right)
{
dist(target -> right, K - 1);
}

}
};