Write a O(n)-time Non-recursive procedure for the preorder traversal of a binary tree.

(a) Write an O(n)-time non-recursive procedure that, given an n-node binary tree, prints out the key of each node of the tree in preorder. Assume that trees consist of vertices of class TreeNode with instance variables parent, left, right, and key. Your procedure takes a TreeNode as its argument (the root of the tree). Use a stack as an auxiliary data structure.

printBinaryTreeNodes(TreeNode root) {}

(b) Explain why your solution works and is O(n).