Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
4th Edition
ISBN: 9780134787961
Author: Tony Gaddis, Godfrey Muganda
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Expert Solution & Answer
Chapter 21, Problem 4AW
Explanation of Solution
Binary search tree:
- Binary search tree is a tree in which the nodes are sorted in the semantic order and it has the shape of binary tree.
- Nodes in the binary search tree can have zero, one, or two children.
- In a binary search tree, any node value is greater than the left sub tree and lesser than the right sub tree.
- Node without children is called a leaf or end node.
- A node that does not have a superior node is called a root node.
- Root node is the starting node.
- The binary search will be performed until finding a search node or reaching the end of the tree.
Step 1: Define a function named “leafCount” with the parameter “btree”.
Step 2: Check if “btree” is equal to null. If it is true, then return 0.
Step 3: Check if “btree.left” is equal to null and “btree.right” is equal to null. If this condition is true, then return 1.
Step 4: If both the condition fails, then return the summation of count of left tree and right tree by calling the function “leafCount ()” recursively...
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Write a method isBST() that takes a Node as argument and returns true if the argument node is the root of a binary search tree, false otherwise.Hint : This task is also more difficult than it might seem, because the order in which youcall the methods in the previous three exercises is important.Write a method isBST() that takes a Node as argument and returns true if the argument node is the root of a binary search tree, false otherwise.Hint : This task is also more difficult than it might seem, because the order in which youcall the methods in the previous three exercises is important.
IN PYTHON
To class Tree, add the following method
public int countLeavesParent(){
return countLeavesParent(root);
{
Write the recursive method
countLeaveParent(Node node) which
returns how many internal nodes in that
are parent of a leave.
Chapter 21 Solutions
Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
Ch. 21.1 - Prob. 21.2CPCh. 21.1 - Prob. 21.3CPCh. 21 - Prob. 1MCCh. 21 - Prob. 2MCCh. 21 - Prob. 3MCCh. 21 - Prob. 4MCCh. 21 - Prob. 5MCCh. 21 - Prob. 6MCCh. 21 - Prob. 7MCCh. 21 - Prob. 8MC
Ch. 21 - Prob. 9MCCh. 21 - Prob. 10MCCh. 21 - Prob. 11TFCh. 21 - Prob. 12TFCh. 21 - Prob. 13TFCh. 21 - Prob. 14TFCh. 21 - Prob. 15TFCh. 21 - Prob. 16TFCh. 21 - Prob. 17TFCh. 21 - Prob. 18TFCh. 21 - Prob. 19TFCh. 21 - Prob. 20TFCh. 21 - Prob. 21TFCh. 21 - Prob. 1FTECh. 21 - Prob. 2FTECh. 21 - Prob. 3FTECh. 21 - Prob. 1SACh. 21 - Prob. 2SACh. 21 - Prob. 3SACh. 21 - Prob. 4SACh. 21 - What is a priority queue?Ch. 21 - Prob. 6SACh. 21 - Prob. 7SACh. 21 - Prob. 1AWCh. 21 - Prob. 2AWCh. 21 - Prob. 3AWCh. 21 - Prob. 4AWCh. 21 - Prob. 5AWCh. 21 - Prob. 6AWCh. 21 - Prob. 7AWCh. 21 - Prob. 4PCCh. 21 - Prob. 6PC
Knowledge Booster
Similar questions
- To class Tree, add the following method public int countOdds(){ return countOddNodes(root); } Write the recursive method countOddNodes(Node n) which returns how many nodes in the tree where thier keys are odd number. Attach File Browse Local Files Browse Content Collectionarrow_forwardCreate a recursive method called isOrdered() that takes a Node and the two keys min and max as arguments. It should return true if all of the tree's keys are between min and max, min and max are, in fact, its smallest and largest keys, respectively, and the BST ordering property holds for all of the tree's keys, and false if it does not.arrow_forwardWrite a recursive private method called countTwoEvenChilds to be included in class BinaryTree as discussed in the lectures. The method counts and returns the number of nodes having two children with even data values in the binary tree. This method is called from a public method countTwoEvenChildsBT, given as follows: public int countTwoEvenChildsBT(){ return countTwoEvenChilds(root); } Method heading: private int countTwoEvenChilds(Node<E> node)arrow_forward
- Write a method that takes any two nodes u and v in a tree T whose root node is s, and quickly determines if the node u in the tree is a descendant or ancestor of node v.arrow_forwardpublic class Node int dataCount; // number of keys with value equal to data stored at this node int treeSize; // number of keys stored in the subtree rooted at this node int data; Node left; Node right; //Get nth largest value of of subtree from the input node. Method to run in o(height) int obtain(Node n, int n){ } Please complete the obtain method in JAVAarrow_forwardWrite a method isBST() that takes a Node as argument and returns true if the argument node is the root of a binary search tree, false otherwise.Hint : This task is also more difficult than it might seem, because the order in which youcall the methods in the previous three exercises is importantarrow_forward
- Java code that eliminates the binary search's node with the lowest value. returns a reference to its element from a tree. If this tree is empty, it raises an EmptyCollectionException. If the tree is empty, returning a reference to the node with the fewest values produces an EmptyCollectionException.arrow_forwardWrite a recursive private method called countDegree to be included in class BinaryTree as discussed in the lectures. If a node is having two child nodes, then its degree is two, if it is having one child node, its degree is one and leaf nodes have degree 0. The method counts and returns the total degree of all the nodes in the binary tree. Example: If a binary tree is having 9 nodes such that 3 nodes, each have 2 child nodes, 2 nodes each have only one child and there are 4 leaf nodes. So, the total degree of the binary tree = 3x2 + 2x1 + 0 = 8. This method is called from a public method countDegreeBT, given as follows: public int countDegreeBT() { return countDegree(root); } Method heading: private int countDegree(Node<E> node)arrow_forwardWrite a recursive buildBinaryTree method that builds a new binary tree from the contents of an array that contains integers. Use the following class definition for a node in a binary tree: class BinaryNode { int element; BinaryNode left; BinaryNode right; } Hint: Take one item from the array and insert it as the root of the tree. Divide the remaining items in half and insert one half in the right subtree and the other half in the left subtree of the root node by calling the method recursively with the relevant array indices.Write a method oddEntries that returns the number of odd integers contained in a binary tree where the element type is int. This method is called with a link to the root node of the tree.arrow_forward
- Write a java method that receives a reference to a binary tree root and finds the node(s) with the maximum value. Your method must return an array describing the nodes containing the maximum value like this: "Right" if the node is a right child to its parent, "Left" if the node is a left child to its parent, and "Root" if the maximum value is in the root. Assume that tree nodes contain integer.arrow_forwardAssume we have an IntBST class, which implements a binary search tree of integers. The field of the class is a Node variable called root that refers to the root element of the tree. Write a method, using recursion or a loop, that returns the smallest element in the tree.arrow_forwardWrite a recursive method body for the static method shown below. Reports the number of text nodes with the same value as val in * the tree. * Gensures * countValText = [the number of nodes in t that are not a tag and have the same value as val] private stațic int çountValȚext(XMLȚree t, String val) (arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education