Consider the following problem which takes as input the root of a binary search tree, and...

Transcribed Image Text:

Consider the following problem which takes as input the root of a binary search tree, and calculates the sum of values in various nodes (including double counting some nodes). static int pathSum (BSTNode root) { return helper (root); } static int helper (BSTNode root) { if (root ==null) { return 0; } int sum=root.value + helper (root.rightChild); if (root.value > 0) sum += helper (root.rightChild); } else sum + helper (root.leftChild); return sum + helper (root. leftChild); Write a recurrence relation for the worst case running time of the helper algorithm if the tree provided as input is a perfect binary tree. Solve the recurrence relation using the Master Theorem. Show your work. (8 points) Definition: A perfect binary tree is a tree in which all internal nodes have two children and all leaves have the same depth. For the purposes of this problem assume that if the size of the tree is n, the left and right subtrees are of size n/2. Consider the following problem which takes as input the root of a binary search tree, and calculates the sum of values in various nodes (including double counting some nodes). static int pathSum (BSTNode root) { return helper (root); } static int helper (BSTNode root) { if (root ==null) { return 0; } int sum=root.value + helper (root.rightChild); if (root.value > 0) sum += helper (root.rightChild); } else sum + helper (root.leftChild); return sum + helper (root. leftChild); Write a recurrence relation for the worst case running time of the helper algorithm if the tree provided as input is a perfect binary tree. Solve the recurrence relation using the Master Theorem. Show your work. (8 points) Definition: A perfect binary tree is a tree in which all internal nodes have two children and all leaves have the same depth. For the purposes of this problem assume that if the size of the tree is n, the left and right subtrees are of size n/2.

Answer rating: 100% (QA)

To write a recurrence relation for the worstcase running time of the helper algorithm when the input ... View the full answer