1. (30 pts) Given a string representing the root of a binary tree (NOTE: Not a BST, there is no sort order) and an integer, return whether or not there is a root-to-leaf path such that adding up all the values along the path equals the integer. Output a 1 if the result is true, and a 0 if the result is false. You must use a Binary Tree implementation (NO STL) for the input to receive credit. Feel free to include any variables you will need in your functions. Case 1: Input 1: 1 2 3 Output 1: 1 3 Case 2: Input 2: 6 7 8 27139 null 1 4 null null null 5 Output 2: 0 20 Case 3: Input 3: 5 4 8 11 null 13 4 72 null null null1 Output 3: 1 22 Assumptions: The given strings will contain no more than 50 inputs. The given input starts at the root and builds the tree sequentially from left to right, as shown below "null" represents an empty space in a given level. The integer to be checked is located on a separate line from the binary tree, and thus can be read in another input or as a separate line in a file. You may use cin/cout or input/output files for submission.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
Need help with this
COSC 2436 Lab 5: Problem Set (60 pts)
Due Date: 9/29/21 at 11:59pm
1. (30 pts) Given a string representing the root of a binary tree (NOTE: Not a BST, there is
no sort order) and an integer, return whether or not there is a root-to-leaf path such that
adding up all the values along the path equals the integer. Output a 1 if the result is true,
and a 0 if the result is false. You must use a Binary Tree implementation (NO STL) for the
input to receive credit. Feel free to include any variables you will need in your functions.
Case 1:
Input 1: 1 2 3
Output 1: 1
3
Case 2:
Input 2: 6 7 827139 null 14 null null null 5
Output 2: 0
20
Case 3:
Input 3: 5 4 8 11 null 13 4 72 null null null 1
Output 3: 1
22
Assumptions: The given strings will contain no more than 50 inputs. The given input
starts at the root and builds the tree sequentially from left to right, as shown below "null"
represents an empty space in a given level. The integer to be checked is located on a
separate line from the binary tree, and thus can be read in another input or as a separate
line in a file. You may use cin/cout or input/output files for submission.
2
4
6.
Example Input: 1 27 5 4 null 9
Output if integer searched = 7: 1
Output if integer searched = 3: 0
Definition of root-to-leaf: A root-to-leaf path is a single path that goes from the root of
the Tree to one of its leaf nodes in a straight line, such that only a single node is traversed
on each level. So if there is a tree with 4 levels, a root-to-leaf path contains at most 4
nodes, but could contain less as long as it reaches a leaf node. The final node is required
to be a leaf node: stopping early is NOT a solution. Valid answers only occur when one
starts at the root and ends at a leaf.
Transcribed Image Text:COSC 2436 Lab 5: Problem Set (60 pts) Due Date: 9/29/21 at 11:59pm 1. (30 pts) Given a string representing the root of a binary tree (NOTE: Not a BST, there is no sort order) and an integer, return whether or not there is a root-to-leaf path such that adding up all the values along the path equals the integer. Output a 1 if the result is true, and a 0 if the result is false. You must use a Binary Tree implementation (NO STL) for the input to receive credit. Feel free to include any variables you will need in your functions. Case 1: Input 1: 1 2 3 Output 1: 1 3 Case 2: Input 2: 6 7 827139 null 14 null null null 5 Output 2: 0 20 Case 3: Input 3: 5 4 8 11 null 13 4 72 null null null 1 Output 3: 1 22 Assumptions: The given strings will contain no more than 50 inputs. The given input starts at the root and builds the tree sequentially from left to right, as shown below "null" represents an empty space in a given level. The integer to be checked is located on a separate line from the binary tree, and thus can be read in another input or as a separate line in a file. You may use cin/cout or input/output files for submission. 2 4 6. Example Input: 1 27 5 4 null 9 Output if integer searched = 7: 1 Output if integer searched = 3: 0 Definition of root-to-leaf: A root-to-leaf path is a single path that goes from the root of the Tree to one of its leaf nodes in a straight line, such that only a single node is traversed on each level. So if there is a tree with 4 levels, a root-to-leaf path contains at most 4 nodes, but could contain less as long as it reaches a leaf node. The final node is required to be a leaf node: stopping early is NOT a solution. Valid answers only occur when one starts at the root and ends at a leaf.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 2 images

Blurred answer
Recommended textbooks for you
Database System Concepts
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education