10) A binary tree with N nodes is at least how deep? How deep is it...


10) A binary tree with N nodes is at least how deep?

How deep is it at most?

12) A Binary Search Tree is a binary tree with what additional property?

13) Beginning with an empty binary search tree, insert the following values 
in the order given.  Draw the tree at each step of the process.

1 10 5 20 22 7

14) Now delete the value 10 from the tree in question 13.  Show each of 
two possible configurations the resulting tree could have.


15) Traverse the value of 14 in post-order and in-order:
Post-order


In-order

17) A certain algorithm to determine the jitter in a data set consists of 2 steps: sorting data (n elements), using merge sort, and computing the sum of differences between all subsequent elements. What's the "big oh'ness" of that algorithm?

Solutions

Expert Solution

Please find the solutions below.


17) A certain algorithm to determine the jitter in a data set consists of 2 steps: sorting data (n elements), using merge sort, and computing the sum of differences between all subsequent elements. What's the "big oh'ness" of that algorithm?

The answer is: O(N²)

venereology answered 10 months ago

Next > < Previous

Related Solutions

Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree...

Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree in level-order. That is, the method should return the root, then the nodes at depth 1, followed by the nodes at depth 2, and so on. Your algorithm should begin by putting the tree root on an initially empty queue. Then dequeue a node, add it to the output, and enqueue its left and right children (if they exist). Repeat until the queue is...

A binary tree model with 7 decision nodes will have how many terminal nodes?

Write a binary search tree with 10 nodes in Java, each node will have 3 attributes...

Write a binary search tree with 10 nodes in Java, each node will have 3 attributes (data, x, y). The binary tree need to have function "add()" to add new node into the tree. After added all 10 nodes, it will be sorted and turn into a balanced binary search tree.

Write a binary search tree and include the functions to find the number of nodes and...

Write a binary search tree and include the functions to find the number of nodes and the height of the tree. Test your code in main. Print the post-order, in-order and pre-order traversal. in c++ please.

a tree is binary, if every node has at most two children nodes. prove that the...

a tree is binary, if every node has at most two children nodes. prove that the maximum of nodes in a binary tree of height h is 2^(h+1)-1

java. Consider a binary tree with integer values in its nodes, implement a method that returns...

java. Consider a binary tree with integer values in its nodes, implement a method that returns the sum of the values contained in all of the nodes of the binary tree with root n.Hint: use recursion.

Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.

For a Binary Search Tree in C++ void setHeight(TNode *n)(10): This method sets the heights of...

For a Binary Search Tree in C++ void setHeight(TNode *n)(10): This method sets the heights of the nodes in a tree. Once a node is inserted, only the node’s ancestors can have their height changed. Thus you should set the height of the node being inserted (to 1) and then adjust the heights of the node’s parent, grandparent, etc. up until either the height of the node doesn’t change or you hit the root.

in a decision tree, decision nodes are the nodes in which uncertainty is involved that is...

in a decision tree, decision nodes are the nodes in which uncertainty is involved that is out of the control of the decision maker. do you agree with the statement? explain with examples. projects may vary with the amount of leverage they will support. for example, acquisitions of real estate or capital equipment are often highly levered , whereas investments in intellectual property are not. do you agree with this statement. explain with examples.

Let T be a binary tree with n positions that is realized with an array representation...

Let T be a binary tree with n positions that is realized with an array representation A, and let f() be the level numbering function of the positions of T, as given in Section 8.3.2. Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot.

Subjects