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.
- The idea is use
stackin 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.
- 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]
- 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