Question

a) Design a recursive linear-time algorithm that tests whether a binary tree is a binary search tree. Describe your algorithm in English or with a simple pseudocode program. b) (3 bonus pts.) Extend the algorithm in a) to test whether a binary tree is an AVL tree.

Answer #1

**Here is the algorithm that checks that a Binary tree is a binary search tree or not -

function BST()

if(root == null)

return 1

if(root -> left != null && maxValue(root -> left) > root -> data)

return 0

if(root -> right != null && maxValue(root -> right) > root -> data)

return 0

if(!BST(root -> left) || !BST(root -> right))

return 0

return 1

**Here is the algorithm that checks that Binary tree is an AVL tree or not -

function AVL()

if(root == null)

return 1

left_height = height(root -> left)

right_height = height(root -> right)

if(abs (left_height - right_height) <= 1 && AVL(root -> left) && AVL(root -> right))

return 1

return 0

Write a C++ program that checks whether a binary search tree is
an AVL. The input is an arbitrary binary search tree, and the
output is binary, so either true or false.

JAVA: Design and implement a recursive version
of a binary search. Instead of using a loop to
repeatedly check for the target value, use calls to a recursive
method to check one value at a time. If the value is not
the target, refine the search space and call the method
again. The name to search for is entered by the user, as
is the indexes that define the range of viable candidates can be
entered by the user (that are passed to...

Design a recursive algorithm with proofs of the following:
Richest Heritage:
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) heritageof 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

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...

Design a recursive algorithm with proofs of the following:
Richest Heritage:
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) heritageof 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 worthand left/right child...

Design a recursive divide-and-conquer algorithm A(n) that takes
an integer input n ≥ 0, and returns the total number of 1’s in n’s
binary representation. Note that the input is n, not its binary
representation. For example, A(9) should return 2 as 9’s binary
representation is 1001, while A(7) should return 3 since 7 is 111
in binary. Note that your algorithm should have a running time of
O(log n). Justify your answer. You need to do the following: (1)...

IN JAVA
Iterative Linear Search, Recursive Binary Search, and
Recursive Selection Sort: <-- (I need the code to be written
with these)
I need Class river, Class CTRiver and Class Driver with
comments so I can learn and better understand the code I also need
a UML Diagram HELP Please!
Class River describes river’s name and its length in miles. It
provides accessor methods (getters) for both variables, toString()
method that returns String representation of the river, and method
isLong()...

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*...

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...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 14 minutes ago

asked 38 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago

asked 4 hours ago

asked 4 hours ago

asked 4 hours ago