Write a O(n)-time Non-recursive procedure for the preorder traversal of a binary
ID: 3748195 • Letter: W
Question
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).
Explanation / Answer
Answer :
(a) O(n)-time non-recursive procedure for the preorder traversal of a binary tree -
void printBinaryTreeNodes(TreeNode root) {
/* Solution in Java since the question mentions the assumption of 'class' TreeNode. This procedure iteratively prints the keys of each node of a binary tree in preorder and returns nothing assuming the procedure takes a TreeNode root as argument */
if (root == null)
return; // base case if root is null
Stack<TreeNode> nodeStack = new Stack<TreeNode>(); // creating a stack of type TreeNode
nodeStack.push(root); // pushing the root of TreeNode in the stack
while (!nodeStack.empty()) {
TreeNode node = nodeStack.peek(); // taking top node of the stack
System.out.print(node.key + " "); // printing the key of the node
nodeStack.pop(); // popping the top node of the stack
if (node.right != null)
nodeStack.push(node.right); // pushing right child of popped node in stack
if (node.left != null)
nodeStack.push(node.left); // pushing left child of popped node in stack
}
}
(b) This is an O(n) solution because the procedure has basically, the first 'if' statement to check null root, which is 1 unit step and has a loop which runs until the stack is empty and thus varies by the number of nodes in the binary tree TreeNode. Provided a n-node binary tree, the loop has 2 'if' statements which means 2 unit steps for each iteration.
Thus taking all the above steps into account -
T(n) = 1 + 2 * n (For each iteration 2 steps, so for n iterations 2 * n steps)
or, T(n) = 1 + 2n = O(n) (Constant values don't change the order of n and hence isn't considered).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.