# Post-order Traversal solution with explanation

• I think of Stack at first glance, and then write this solution.
My idea is that this problem ask to find a Lowest Common Parent node. With Stack and post-order traversal, we can keep the parent node in the Stack.

Every time a node is visited (which means they will never get into the Stack), the code will check if it is a target node.

• For the first found node, we use one node lcp to remember the parent of it.
• If the current lcp is removed before we find the second target node, lcp will be replaced by its parent.

p.s. there are in fact only 2 situation

1. Target node p is a parent/ancestor of node q
2. They are separately in left subtree and right subtree.
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
// Post-order traversal

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lcp = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root, pre = null;
int count = 0;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur.right == null || cur.right == pre) {
if (cur == p || cur == q) {
count++;
if (count == 1) lcp = stack.peek(); // !stack.isEmpty();
if (count == 2) return lcp;
}
if (cur == lcp) lcp = stack.peek(); // !stack.isEmpty();
pre = cur;
cur = null;
} else {
stack.push(cur);
cur = cur.right;
}
}
}
return lcp;
}
}
``````

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