Binary Search Tree

From the answer group below, select the correct combination of answers to be inserted into A and B in the program.

The function isPerfectBinaryTree checks whether the binary tree with a given root node is perfect. In a perfect binary tree, all the internal nodes have exactly two children, and all leaf nodes are at the same level. The function returns true if the tree is perfect, or false otherwise.
The class Node models a node of a binary tree as described in Table 1. A Node-type variable holds a reference to an instance of the class Node.

Table 2 describes the functions used in the program.

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

Binary Search Trees (BST) are a fundamental data structure where each node has at most two children: a left child and a right child. The key property of a BST is that each value of all nodes in its left subtree are less than the value of the node, and each value of all nodes in its right subtree are greater than the value of the node. The table shows the member variables of the class Node. Node-type variable holds a reference to an instance of the class Node. Each node in a BST has a different value.

The function remove removes a node with the same key value as the argument key from the BST specified by the argument node and returns the resulting BST. The function searches for a node with the same key value, and if the found node (call it X here) does not have a right subtree, the function returns its left subtree. If X has a right subtree, the function locates the node (call it Y here) with the smallest key value in the right subtree, replaces the key value of X with that of Y, and then removes Y. If there is no node with the same key value in the BST, the function performs no operations. The procedure test demonstrates this behavior by removing 1 node from a BST containing 7 nodes. The figure shows the BST before and after node removal.

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

Given the root of two binary trees, the aim of the following program is to check whether these two trees are identical. Two binary trees are defined as identical if they satisfy the following formal conditions:

• •Structure: Both trees have the same structure, implying that for every corresponding node in the two trees, the arrangement of the left and right children is the same.
• •Node Values: Each corresponding node in the two trees must contain the same value. Specifically, if tree T₁ has a node N₁ with value v₁ and tree T₂ has the corresponding node N₂ with value v₂, then v₁ = v₂.

The function isSameTree takes two instances of class TreeNode as the argument representing the root nodes of two binary trees, and returns true if the trees are identical, or false otherwise. The member variables of TreeNode are listed in the table below:

From the answer group below, select the correct combination of answers to be inserted into A through C in the program. Here, the array index starts at 1.

The procedure preorder traverses a binary tree and outputs the value of each node by following the sequence: root, left subtree, and right subtree using a stack (Last In, First Out). Each node of the binary tree is represented by the class Node. The table shows the description of the class Node. The Node-type variable holds a reference to an instance of the class Node. The argument root holds a reference to the root of the binary tree, which is an instance of the class Node. In the program, areas outside of the array must not be referenced.