Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
- Recursive Functions. A regular binary tree is a binary tree whose internal nodes have exactly two subtrees. Write recursive functions to compute the following attributes of a regular binary tree; show the trace of execution of each function on the following tree. Assume that you have a Boolean function that tells you whether a node is a leaf. 1. The number of leaves in the tree. 2. The number of arcs in the tree. 3. The number of nodes in the tree. 4. The height of the tree (i.e. the longest distance from the root to any leaf). D B H E A 1 F C G

- Recursive Functions. A regular binary tree is a binary tree whose internal nodes have exactly two subtrees. Write recursive functions to compute the following attributes of a regular binary tree; show the trace of execution of each function on the following tree. Assume that you have a Boolean function that tells you whether a node is a leaf. 1. The number of leaves in the tree. 2. The number of arcs in the tree. 3. The number of nodes in the tree. 4. The height of the tree (i.e. the longest distance from the root to any leaf). D B H E A 1 F C G

icon
Related questions
Question
Please Help ASAP!!
Recursive Functions. A regular binary tree is a binary tree whose internal nodes have exactly two subtrees. Write recursive functions to compute the following attributes of a regular binary tree; show the trace of execution of each function on the following tree. Assume that you have a Boolean function that tells you whether a node is a leaf. 1. The number of leaves in the tree. 2. The number of arcs in the tree. 3. The number of nodes in the tree. 4. The height of the tree (i.e. the longest distance from the root to any leaf). D B H E A F C G th of computes the number of internal nodes of a regular binary tre
Transcribed Image Text:Recursive Functions. A regular binary tree is a binary tree whose internal nodes have exactly two subtrees. Write recursive functions to compute the following attributes of a regular binary tree; show the trace of execution of each function on the following tree. Assume that you have a Boolean function that tells you whether a node is a leaf. 1. The number of leaves in the tree. 2. The number of arcs in the tree. 3. The number of nodes in the tree. 4. The height of the tree (i.e. the longest distance from the root to any leaf). D B H E A F C G th of computes the number of internal nodes of a regular binary tre
Hint: below is a function that computes the number of internal nodes of a regular binary tree, and its trace of execution on the sample tree. int internal Nodes(treeType t) {if leaf(t) {return 0;} else {return 1+internal Nodes(t.left)+internal Nodes(t.right);}} Trace of execution: internal Nodes (A) = 1 + internalNodes(B) + internalNodes(C) = 1 + 1 + internal Nodes (D) + internalNodes(E) + + 1 + internal Nodes (F) + internalNodes(G) = 1 + 1 + 0 + internal Nodes(E) + +1+0+0 = 1 + 1 + 0 + 1 + internalNodes (H) + internalNodes(1) +1+0+0 = 1+1+0+1+0+0 +1+0+0 = 4.
Transcribed Image Text:Hint: below is a function that computes the number of internal nodes of a regular binary tree, and its trace of execution on the sample tree. int internal Nodes(treeType t) {if leaf(t) {return 0;} else {return 1+internal Nodes(t.left)+internal Nodes(t.right);}} Trace of execution: internal Nodes (A) = 1 + internalNodes(B) + internalNodes(C) = 1 + 1 + internal Nodes (D) + internalNodes(E) + + 1 + internal Nodes (F) + internalNodes(G) = 1 + 1 + 0 + internal Nodes(E) + +1+0+0 = 1 + 1 + 0 + 1 + internalNodes (H) + internalNodes(1) +1+0+0 = 1+1+0+1+0+0 +1+0+0 = 4.
Expert Solution
steps

Step by step

Solved in 4 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer