# Pre

Before we try to convert any recursive algo into non-recursive, we should be familiar to recursive and non-recursive version of binary tree traversal.

Read binary tree traversal to recap.

# Key points

- The idea is use
`stack`

in heap to mimic the behavior of function call stack. - For post-order traversal, since we need to update parent’s state from child node, we will need to push state of parent along with child node into stack. We will explain this later with example.

# Post order

## Code skeleton

1 | class Solution: |

- Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

1 | class Solution: |

## More example

- 236. Lowest Common Ancestor of a Binary Tree
- 979. Distribute Coins in Binary Tree
- 297. Serialize and Deserialize Binary Tree
- 108. Convert Sorted Array to Binary Search Tree
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 110. Balanced Binary Tree
- 114. Flatten Binary Tree to Linked List