C++ How to Program (10th Edition)
10th Edition
ISBN: 9780134448237
Author: Paul J. Deitel, Harvey Deitel
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
Chapter 19, Problem 19.19E
Program Plan Intro
Number of Levels that a Binary Tree Has
Program Plan:
1. Construct a tree with a root node, and 4 leaf nodes
2. Find the depth of the left subtree in a recursive manner if the tree is not null
3. Find the depth of the right subtree in a recursive manner if the tree is not null
4. Determine the maximum value of the depths of both subtrees
5. Add 1 to the resulting value for the current node
6. Return depth of the root node to get the number of levels in the given binary tree.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Don't reject
Language/Type:
C++ binary trees pointers recursion
Write a function named hasPath that interacts with a tree of BinaryTreeNode structures representing an unordered binary tree. The function accepts three parameters: a pointer to the root of the tree, and two integers start and end, and returns true if a path can be found in the tree from start down to end. In other words, both start and end must be element data values that are found in the tree, and end must be below start, in one of start's subtrees; otherwise the function returns false. If start and end are the same, you are simply checking whether a single node exists in the tree with that data value. If the tree is empty, your function should return false.
For example, suppose a BinaryTreeNode pointer named tree points to the root of a tree storing the following elements. The table below shows the results of several various calls to your function:
67
88
52
1
21
16
99
45
Call
Result
Reason
hasPath(tree,
67, 99)
true
path exists…
Use function def showList(self)
Precondition: None.
Postcondition: Outputs the keys of the elements of the order list. If the list is empty, outputs “Empty list”
note: Use python and the concept of doubly Linked List
Chapter 19 Solutions
C++ How to Program (10th Edition)
Ch. 19 - Prob. 19.6ECh. 19 - Prob. 19.7ECh. 19 - Prob. 19.8ECh. 19 - Prob. 19.9ECh. 19 - Prob. 19.10ECh. 19 - Prob. 19.11ECh. 19 - (Infix-to-Post fix conversion) Stacks are used by...Ch. 19 - Prob. 19.13ECh. 19 - Prob. 19.14ECh. 19 - Prob. 19.15E
Ch. 19 - Prob. 19.16ECh. 19 - Prob. 19.17ECh. 19 - (Duplicate Elimination) In this chapter, we saw...Ch. 19 - Prob. 19.19ECh. 19 - Prob. 19.20ECh. 19 - Prob. 19.21ECh. 19 - Prob. 19.22ECh. 19 - Prob. 19.23ECh. 19 - Prob. 19.24ECh. 19 - Prob. 19.25ECh. 19 - Prob. 19.26ECh. 19 - Prob. 19.27ECh. 19 - Prob. 19.28E
Knowledge Booster
Similar questions
- quick Solution pleasearrow_forward1.) Design a Binary Search Tree ADT by using following functions. Include the function definitions & run the program (Kindly include header files as well). Paste the output as a screenshot and write the code in your answer sheet. insert(int val)find(int x)************************************************************************************ class btNode { public: int info; btNode *lLink; btNode *rLink; btNode(int e, btNode *l = NULL, btNode *r = NULL) { info = e; lLink = l; rLink = r; } btNode() { lLink = NULL; rLink = NULL; } }; class binarySTADT { private: btNode *root; int count = 0; public: binarySTADT() { root = NULL; } void insert(int val); // function to insert a given value in the tree.…arrow_forwardC in pythonarrow_forward
- Instructions. c++ binary search trees. 1. Implement a function that will build a binary search tree. 2. Using the function above create a binary search tree. 3. Implement a swapSubtrees() function that will take a pointer to a root node and a target value. Function will search for the target value in the tree and swap all left nodes with right nodes for all descendant nodes. 4. Pass the tree created in step 2 to test swapSubtrees() function. 5. You can use the inorder, postorder or preorder traversal implemented in class to display and confirm the logic. (trace it by hand as well) TreeNode{ int val; TreeNode* left = nullptr; TreeNode* right = nullptr; TreeNode(){} TreeNode(int val): val(val){} };arrow_forwardC using pythonarrow_forward*Please using JAVA only* Objective Program 3: Binary Search Tree Program The primary objective of this program is to learn to implement binary search trees and to combine their functionalities with linked lists. Program Description In a multiplayer game, players' avatars are placed in a large game scene, and each avatar has its information in the game. Write a program to manage players' information in a multiplayer game using a Binary Search (BS) tree for a multiplayer game. A node in the BS tree represents each player. Each player should have an ID number, avatar name, and stamina level. The players will be arranged in the BS tree based on their ID numbers. If there is only one player in the game scene, it is represented by one node (root) in the tree. Once another player enters the game scene, a new node will be created and inserted in the BS tree based on the player ID number. Players during the gameplay will receive hits that reduce their stamina. If the players lose…arrow_forward
- 1. Do some research about binary search trees. 2. Create a structure in C for the nodes of this tree. Which variables do the structure have? 3. Write a function that builds a balanced binary search tree. The input argument of this function is a sorted array of integers. 4. Write a recursive function that inserts a new element to the tree. The input argument of this function is a pointer to the head node of the tree. 5. What is the time complexity of this insertion function?arrow_forwardcode:arrow_forwardComplete the following ():a. A stack is used by the system when a function call is madeb. A stack can become full during program executionarrow_forward
- -- > In C++ write a program without using classes, and build in functions, only use structure.!!!!!! Populate a tree via a text file (input.txt) Make sure that after every insert, the tree is balanced.At the end, display the tree in level format. Make sure to include the height and the balancefactor of every node in your output. Redirect the display to an output file (output.txt)Hint://I will not accept any other algorithm//This is not a recursive algorithmnode * rebalance(node *node){node->height = max(height(node->left), height(node->right)) + 1;int balance = getBalance(node); //node->left - node->right/*do rotations as necessaryIf Left heavy outside : return rightRotate(node);If right heavy outside: return leftRotate(node);If left heavy inside: left rotation first, right rotation 2nd, return top nodenode->left = leftRotate(node->left);return rightRotate(node);if right heavy inside: right rotation first, left rotation 2nd, return top nodenode->right =…arrow_forwardC++ Data Structures (Binary Trees)- Write the definition of the function nodeCount that returns the number of nodes in the binary tree. Add this function to the class binaryTreeType and create a program to test this function. Here are the headers: binaryTree.h //Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: const binaryTreeType<elemType>& operator= (const binaryTreeType<elemType>&); //Overload the assignment operator. bool isEmpty() const; //Function to determine whether the binary tree is empty. //Postcondition: Returns true if the binary tree is empty; // otherwise, returns false. void inorderTraversal() const; //Function to do an inorder…arrow_forward2. Write the following recursive expression tree functions a. Prefix b. Infix c. Postfix d. Evaluate (Evaluate the expression tree-return the value)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