Question

Homework 3 CSE 214: Data Structures State University of New York at Stony Brook Instructor: Prof. Pramod Ganapathi Total points = 100. Total questions = 3. Total pages = 1. Submit the single PDF on Brightspace before the deadline. Designing an algorithm means giving: (i) pseudocode covering all corner cases, (ii) diagrams to visualize the working of the algorithm (e.g. dry-run for some examples), (iii) time and space complexity analysis. 1. (a) [4 points] Draw the binary tree representation of the following arithmetic expression: (((5 + 2) × (2 − 1))/((2 + 9) + ((7 – 2) — 1)) × 8) (b) [6 points] Draw a binary tree T that simultaneously satisfies the following: (i) Each internal node of T stores a single character. (ii) A preorder traversal of T yields EXAMFUN. (iii) An inorder traversal of T yields MAFXUEN. 2. Given a binary tree: (a) [10 points] Design an efficient recursive algorithm COUNTNODES (Node curr) to count the number of nodes in the tree. (b) [10 points] Design an efficient recursive algorithm COUNTLEAF NODES(Node curr) to count the number of leaf nodes in the tree. (c) [10 points] Design an efficient recursive algorithm COUNTNONLEAF NODES (Node curr) to count the number nonleaf of nodes in the tree. (d) [10 points] Design an efficient recursive algorithm FINDHEIGHT(Node curr) to find the height of the tree. (e) [10 points] Design an efficient recursive algorithm ISBINARYSEARCHTREE (Node curr) to check if the tree is a binary search tree. (f) [10 points] Design an efficient algorithm to check if the array representation of a binary tree ISBINARYSEARCHTREE(A[1...n]) represents a binary search tree. 3. Given a binary search tree: (a) [10 points] Design an efficient recursive algorithm FINDMINIMUMNODE(Node curr) to find the node with the minimum key in the tree. (b) [20 points] Design an efficient recursive algorithm PRINTELEMENTSINRANGE(Node curr, [a, b]) to print all the elements in the tree that are in the range. 1

Get Instant Homework HelpOn Your Mobile

Get Instant Homework HelpOn Your Mobile

Get Instant Homework HelpOn Your Mobile