Binary Tree Deletion Order
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
Given the root of a binary tree, return the node values in a safe deletion order: every child must appear before its parent.
When both children exist, delete the entire left subtree before the right subtree, then delete the parent. Values need not be unique. Return an empty array for an empty tree.
Your final solution must avoid recursion so that a deeply skewed tree cannot overflow the call stack.
Function
deleteTreeOrder(root: TreeNode) → int[]Examples
Example 1
root = [1,2,3,null,4]return = [4,2,3,1]Delete leaf 4 before its parent 2, then the right subtree rooted at 3, and finally root 1.
Example 2
root = []return = []An empty tree has no deletion operations.
Example 3
root = [7]return = [7]A leaf can be deleted immediately.
Constraints
0 <= node count <= 200000.-10^9 <= node.val <= 10^9.