# Post-order traversal recursive solution in C++

• What we need to do here is to do post-order traversal and the visit function is to check whether root is p or q. In the following code, once we find p or q, we reset p or q to nullptr to indicate that p or q is found.
If both p and q are found in a left subtree, then just return the root (when p and q are both found at the first time). If p and q are found in different subtrees of root, then return root. If both p and q are both found in a right subtree, return the root when they are found first time .

``````class Solution {
private:
TreeNode* dfs(TreeNode* root, TreeNode* &p, TreeNode* &q)
{
bool retRoot=false; // true means only one of p and q is found in the left subtree
if(!root) return root;
TreeNode* res;
res = dfs(root->left, p, q); // search the left subtree
if(!p && !q) return res; // if found both p and q, return the root when they are found first time
if (!p || !q) retRoot = true; // check if one of p and q is found in the left tree
res = dfs(root->right, p, q); // search the right subtree
if(!p && !q)  // if we found both p and q
return  retRoot?root:res; // if one is in the left subtree and the other is in the right subtree, return root, otherwise both of them are in the right subtree, so return the root when they first time are found
if(root==p) p =nullptr;  // check whether root is p or q
else if (root==q) q=nullptr;
return root;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return dfs(root, p, q);
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.