Question

Consider a binary search tree where each tree node v has a field v.sum which stores...

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v. We wish to add an operation SumLE(K) to this binary search tree which returns the sum of all the keys in the tree whose values are less than or equal to K.

(a) Describe an algorithm, SumLE(K), which returns the sum of all the keys in the tree whose values are less than or equal to K. Give pseudo-code for your algorithm. Your algorithm should take the same time as operation TreeSearch.

procedure TreeSearch(x,K)

1 if (x = NIL) or (K = x.key) then

2 return (x);

3 else if (K < x.key) then

4 TreeSearch(x.left, K);

5 else

6 TreeSearch(x.right, K);

7 end

-------------------------

(b) Explain why your algorithm is correct, i.e., why it returns the sum of all the keys whose values are less than or equal to K.

(c) Analyze the running time of your algorithm in terms of the size n and height h of the binary search tree.

Homework Answers

Answer #1

(a)
procedure SumLE(x,K)

if (x = NIL) or (K = x.key) then
   rightSum = 0
   if x.right = NIL
       rightSum = 0
   else
       rightSum = (x.right).sum + (x.right).key
   return x.sum - rightSum + x.key
else if (K < x.key) then
   SumLE(x.left,K);
else
   SumLE(x.right,K);
end

(b) In a Binary Search Tree, all the keys in the right sub tree are greater than the root and left sub tree are less than the root. So for SumLE we need sum of all the keys in its left subtree. That is exactly what we achieved.

(c) This takes same time as Searching in a tree. The time taken will be O(logn), where n is the number of nodes in the tree.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
‏What is the output of the Euler tour in the normal binary search tree if the...
‏What is the output of the Euler tour in the normal binary search tree if the key insert order is 5 , 2 , 8 , 5 , 9 , 5 , 1 , 3 , 4 , 2 , 8 ? All keys equal to the node should be the right subtree of that node. ____________________________________________________________ ‏Construct the binary max - heap for the keys given below. Once all the keys are inserted, perform the remove maximum operation, and...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
You are given a reference to the root node of a binary search tree, that implements...
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single...
Input: A binary tree T in which each node x contains a field worth[x], which is...
Input: A binary tree T in which each node x contains a field worth[x], which is a (positive, zero, or negative) monetary value expressed as a real number. Define (monetary) heritage of a node x to be the total worth of ancestors of x minus the total worth of proper descendants of x. Output: A node x in T with maximum heritage. Note: other than the field worth and left/right child pointers, nodes of the given tree do not have...
Let T be a complete binary tree such that node v stores the entry (p(v), 0),...
Let T be a complete binary tree such that node v stores the entry (p(v), 0), where p(v) is the level number of v. Is tree T a heap? Why or why not? I know that a complete binary tree is a heap, but shouldn't we also take into consideration the values that it is storing into the tree: (p(v), 0)? The heap tree could be either a min-heap or max-heap. If we order the the value based of p(v)...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
This assignment involves using a binary search tree (BST) to keep track of all words in...
This assignment involves using a binary search tree (BST) to keep track of all words in a text document. It produces a cross-reference, or a concordance. This is very much like assignment 4, except that you must use a different data structure. You may use some of the code you wrote for that assignment, such as input parsing, for this one. Remember that in a binary search tree, the value to the left of the root is less than the...
Copy the file SimplerBST.java from the week 1 examples package and rename the file and class...
Copy the file SimplerBST.java from the week 1 examples package and rename the file and class A3BST. Add two public methods: one named countTwins that takes no parameters and that, when called, traverses every node of the tree to count the number of nodes having two children. one named lessThanValueCount that takes a paremeter of generic type V, and that, when called, traverses every node of the tree to count the number of nodes whose value (not its key) is...
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in...
CRYPTOGRAPHY PROBABILITY DISTRIBUTION Bad Shuffles Consider the following card shuffling algorithm. There are three cards in the deck and they are each represented by an element in {X, Y, Z}. [Bonus marks if you use the deck {W, X, Y, Z}] Algorithm Shuffle --------------------------------------------------- deck := [X,Y,Z] for i from 0 to 2 do j := RANDOM(i) swap values of deck[i] and deck[j] end for return deck --------------------------------------------------- For each of the following definitions of RANDOM(i), compute the probability distribution...