Binary Trees. Recall that a binary tree is defined as a finite set of nodes that
ID: 3667450 • Letter: B
Question
Binary Trees. Recall that a binary tree is defined as a finite set of nodes that is either empty or consists of a root and two disjoint binary trees T_L, and T_R, respectively, the left and right subtree of the root. Since the definition itself divides a binary tree into two smaller structures of the same type, the left and the right subtree, many problems about binary trees can be solved by applying the divide-and-conquer technique. Height: The height of a binary tree is defined as the length of the longest path from the root to a leaf (i.e., count the edges in the path not the nodes). Write pseudocode for a divide-and-conquer algorithm that returns the height of a binary tree T. The function should return -1 as the height of an empty tree. Write a recurrence to count the number of comparisons made to compute the height in part (a) and solve it exactly. Leaf: A node in a binary tree with no children is a leaf node. Write pseudocode for a divide-and-conquer algorithm that returns the number of leaves in a binary tree T.Explanation / Answer
Height:
(a)
int Height(root)
{
leftHeight= Height(root->left)
rightHeight= Height(root->right)
return max(leftheight,rightheight)+1
}
(b) T(n) = T(a) + T(n-a-1)
I assume that a nodes are in the left subtree and hence n-a-1 nodes are in the right subtree
Leaf:
(a)
int leaf(root)
{
if node == NULL
return 0;
if node->right == NULL and node->left == NULL
return 1;
return leaf(node->left) + leaf(node->right)
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.