How should I practice Binary Tree Preorder Traversal with O(1) Auxiliary Space?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Bloomberg LP phone screen problems in FastPrep.

Is Binary Tree Preorder Traversal with O(1) Auxiliary Space associated with Bloomberg LP?

FastPrep tags this as a Bloomberg LP phone screen coding practice problem when the problem catalog has that company and stage context.

Binary Tree Preorder Traversal with O(1) Auxiliary Space

Bloomberg LP● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

Given the root of a binary tree, return its preorder traversal values: root, then left subtree, then right subtree.

Use Morris traversal so the algorithm uses O(1) auxiliary space apart from the returned array. Every temporary pointer must be restored before returning.

Function

preorderTraversal(root: TreeNode) → int[]

Examples

Example 1

root = [1,null,2,3]return = [1,2,3]

Visit the root, then the right subtree whose left child is three.

Example 2

root = []return = []

An empty tree has an empty traversal.

Constraints

The tree contains between 0 and 10^5 nodes.
-10^9 <= Node.val <= 10^9.