(10 points) Use a recurrence relation to show that the running time of the printPreorder method in Figure 18.22 is O(N). You may assume that the tree is perfect (i.e., full, balanced, and size 2^k - 1 for some integer k).

figure 18.22 1Print tree rooted at current node using preorder traversal 2 public void printPre0rder) Routines for printing nodes in preorder postorder, and inorder // Node // Left // Right System.out.println element); if( left != null ) 5 left.printPre0rder if( right != null ) right.printPre0rder(); 9 10 11 / Print tree rooted at current node using postorder traversal. 12 public void printPost0rder) 13 // Left // Right // Node if( left != null ) left.printPost0rder(); 15 16 17 18 19 20 21 / Print tree rooted at current node using inorder traversal 22 public void printInOrder) 23 24 25 26 27 28 if( right != null ) right.printPost0rder; System.out.println element); // Left // Node // Right if( left != null ) left.printInorder; System.out.println element); if( right ! null ) right.printInOrder)