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 solutionStudents 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
- Create 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_forwardWrite 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_forward
- public 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_forwardJava 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_forward
- Write 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_forwardWrite a recursive function that increments by one the value for every node in the binary tree pointed at by root, then returns the modified tree. Assume that nodes store integer values. Here are methods that you can use on the BinNode objects: interface BinNode { public int value(); public void setValue(int v); public BinNode left(); public BinNode right(); public boolean isLeaf(); } public BinNode BTinc(BinNode root){ }arrow_forwardHey, please complete the sample question below using either pseudocode or Java.arrow_forward
- Write a BinaryTreeUtils class with the following methods: A) size(tree) – the number of nodes in the tree B) height(tree) – the height of the treearrow_forwardBelow is the IntTree class we discussed in week 3 and that you worked on in HW3. We are in the middle of implementing a new recursive method called leafCount that should return the number of leaves in the tree. What code should replace the comment /* recursive case */ so that the leafCount method works correctly? return tempL + 1; return tempL + tempR + 1; return tempL + tempR; return tempR + 1;arrow_forwardWritten in Java The diameter D of a binary tree is defined as the number of nodes on the longest path between any two nodes in the tree. The path may pass through the root, but does not have to. For a given diameter, there may be more than one path which has the longestlength. For example, the following tree has diameter of 5: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 EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable 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