Q1 - 50 pts) A binary tree is a complete binary tree if all the internal nodes (
ID: 3607379 • Letter: Q
Question
Q1 - 50 pts) A binary tree is a complete binary tree if all the internal nodes (including the root node) have exactly two child nodes and all the leaf nodes are at level 'h' corresponding to the height of the tree.
Consider the code for the binary tree given to you for this question. Add code in the blank space provided for the member function checkCompleteBinaryTree( ) in the BinaryTree class. This member function should check whether the binary tree input by the user (in the form of the edge information stored in a file) is a complete binary tree.
Draw the two binary trees (along with their node ids) that you have come up with, include the text files (corresponding to these two binary trees) that are input to the program and the complete C++.
To test your code, come up with two binary trees of at least 12 vertices: one, a complete binary tree and another, a binary tree that is not a complete tree.
Prepare the input file for the two binary trees and input them to the code for this question. Capture the screenshots of the outputs.
#include <iostream>
#include <fstream>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
#include <algorithm> // max function
using namespace std;
class BTNode{
private:
int nodeid;
int data;
int levelNum;
BTNode* leftChildPtr;
BTNode* rightChildPtr;
public:
BTNode(){}
void setNodeId(int id){
nodeid = id;
}
int getNodeId(){
return nodeid;
}
void setData(int d){
data = d;
}
int getData(){
return data;
}
void setLevelNum(int level){
levelNum = level;
}
int getLevelNum(){
return levelNum;
}
void setLeftChildPtr(BTNode* ptr){
leftChildPtr = ptr;
}
void setRightChildPtr(BTNode* ptr){
rightChildPtr = ptr;
}
BTNode* getLeftChildPtr(){
return leftChildPtr;
}
BTNode* getRightChildPtr(){
return rightChildPtr;
}
int getLeftChildID(){
if (leftChildPtr == 0)
return -1;
return leftChildPtr->getNodeId();
}
int getRightChildID(){
if (rightChildPtr == 0)
return -1;
return rightChildPtr->getNodeId();
}
};
class Node{
private:
int data;
Node* nextNodePtr;
Node* prevNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return data;
}
void setNextNodePtr(Node* nodePtr){
nextNodePtr = nodePtr;
}
Node* getNextNodePtr(){
return nextNodePtr;
}
void setPrevNodePtr(Node* nodePtr){
prevNodePtr = nodePtr;
}
Node* getPrevNodePtr(){
return prevNodePtr;
}
};
class Queue{
private:
Node* headPtr;
Node* tailPtr;
public:
Queue(){
headPtr = new Node();
tailPtr = new Node();
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
Node* getHeadPtr(){
return headPtr;
}
Node* getTailPtr(){
return tailPtr;
}
bool isEmpty(){
if (headPtr->getNextNodePtr() == 0)
return true;
return false;
}
void enqueue(int data){
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(0);
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr == 0){
headPtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(0);
}
else{
lastNodePtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(lastNodePtr);
}
tailPtr->setPrevNodePtr(newNodePtr);
}
int dequeue(){
Node* firstNodePtr = headPtr->getNextNodePtr();
Node* nextNodePtr = 0;
int poppedData = -100000; //empty queue
if (firstNodePtr != 0){
nextNodePtr = firstNodePtr->getNextNodePtr();
poppedData = firstNodePtr->getData();
}
else
return poppedData;
if (nextNodePtr != 0){
nextNodePtr->setPrevNodePtr(0);
headPtr->setNextNodePtr(nextNodePtr);
}
else{
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
return poppedData;
}
int peek(){
Node* firstNodePtr = headPtr->getNextNodePtr();
if (firstNodePtr != 0)
return firstNodePtr->getData();
else
return -100000; //empty queue
}
};
class BinaryTree{
private:
int numNodes;
BTNode* arrayOfBTNodes;
public:
BinaryTree(int n){
numNodes = n;
arrayOfBTNodes = new BTNode[numNodes];
for (int id = 0; id < numNodes; id++){
arrayOfBTNodes[id].setNodeId(id);
arrayOfBTNodes[id].setLevelNum(-1);
arrayOfBTNodes[id].setLeftChildPtr(0);
arrayOfBTNodes[id].setRightChildPtr(0);
}
}
void setLeftLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setLeftChildPtr(&arrayOfBTNodes[downstreamNodeID]);
}
void setRightLink(int upstreamNodeID, int downstreamNodeID){
arrayOfBTNodes[upstreamNodeID].setRightChildPtr(&arrayOfBTNodes[downstreamNodeID]);
}
void printLeafNodes(){
for (int id = 0; id < numNodes; id++){
if (arrayOfBTNodes[id].getLeftChildPtr() == 0 && arrayOfBTNodes[id].getRightChildPtr() == 0)
cout << id << " ";
}
cout << endl;
}
bool isLeafNode(int nodeid){
if (arrayOfBTNodes[nodeid].getLeftChildPtr() == 0 && arrayOfBTNodes[nodeid].getRightChildPtr() == 0)
return true;
return false;
}
int getNodeHeight(int nodeid){
if (nodeid == -1 || isLeafNode(nodeid) )
return 0;
int leftChildID = arrayOfBTNodes[nodeid].getLeftChildID(); // -1 if not exist
int rightChildID = arrayOfBTNodes[nodeid].getRightChildID(); // -1 if not exist
return max(getNodeHeight(leftChildID), getNodeHeight(rightChildID)) + 1;
}
int getTreeHeight(){
return getNodeHeight(0);
}
void assignLevelNumbers(){
Queue queue;
queue.enqueue(0);
arrayOfBTNodes[0].setLevelNum(0);
while (!queue.isEmpty()){
int firstNodeInQueue = queue.dequeue();
int leftChildID = arrayOfBTNodes[firstNodeInQueue].getLeftChildID();
if (leftChildID != -1){
queue.enqueue(leftChildID);
arrayOfBTNodes[leftChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);
}
int rightChildID = arrayOfBTNodes[firstNodeInQueue].getRightChildID();
if (rightChildID != -1){
queue.enqueue(rightChildID);
arrayOfBTNodes[rightChildID].setLevelNum(arrayOfBTNodes[firstNodeInQueue].getLevelNum()+1);
}
}
}
int getDepth(int nodeid){
return arrayOfBTNodes[nodeid].getLevelNum();
}
bool checkCompleteBinaryTree(){
// Need to do three things
// (1) Get the height of the tree
// (2) Assign the level numbers for each node
// (3) If a node is not a leaf node (i.e., an internal node), check if its has two child nodes
// If a node is a leaf node, check if its level number equals the height of the tree
}
};
int main(){
string filename;
cout << "Enter a file name: ";
cin >> filename;
int numNodes;
cout << "Enter number of nodes: ";
cin >> numNodes;
BinaryTree binaryTree(numNodes);
ifstream fileReader(filename);
if (!fileReader){
cout << "File cannot be opened!! ";
return 0;
}
int numCharsPerLine = 10;
char *line = new char[numCharsPerLine];
// '10' is the maximum number of characters per line
fileReader.getline(line, numCharsPerLine, ' ');
// ' ' is the delimiting character to stop reading the line
while (fileReader){
char* cptr = strtok(line, ",: ");
string upstreamNodeToken(cptr);
int upstreamNodeID = stoi(upstreamNodeToken);
cptr = strtok(NULL, ",: ");
int childIndex = 0; // 0 for left child; 1 for right child
while (cptr != 0){
string downstreamNodeToken(cptr);
int downstreamNodeID = stoi(downstreamNodeToken);
if (childIndex == 0 && downstreamNodeID != -1)
binaryTree.setLeftLink(upstreamNodeID, downstreamNodeID);
if (childIndex == 1 && downstreamNodeID != -1)
binaryTree.setRightLink(upstreamNodeID, downstreamNodeID);
cptr = strtok(NULL, ",: ");
childIndex++;
}
fileReader.getline(line, numCharsPerLine, ' ');
}
if (binaryTree.checkCompleteBinaryTree())
cout << "The binary tree is a complete binary tree " << endl;
else
cout << "The binary tree is not a complete binary tree " << endl;
return 0;
}
Explanation / Answer
PGM1:
. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.
For example, in the following case, tree S is a subtree of tree T.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
Solution: Traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
Following is the implementation for this.
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if (root1 == NULL && root2 == NULL)
return true;
if (root1 == NULL || root2 == NULL)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right) );
}
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;
if (T == NULL)
return false;
/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||
isSubtree(T->right, S);
}
/* Helper function that allocates a new node with the given data
and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above function */
int main()
{
// TREE 1
/* Construct the following tree
26
/
10 3
/
4 6 3
30
*/
struct node *T = newNode(26);
T->right = newNode(3);
T->right->right = newNode(3);
T->left = newNode(10);
T->left->left = newNode(4);
T->left->left->right = newNode(30);
T->left->right = newNode(6);
// TREE 2
/* Construct the following tree
10
/
4 6
30
*/
struct node *S = newNode(10);
S->right = newNode(6);
S->left = newNode(4);
S->left->right = newNode(30);
if (isSubtree(T, S))
printf("Tree 2 is subtree of Tree 1");
else
printf("Tree 2 is not a subtree of Tree 1");
getchar();
return 0;
}
Output:
Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.
We can solve the above problem in O(n) time. Please refer Check if a binary tree is subtree of another binary tree | Set 2 for O(n) solution.
PGM2:
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
Examples:
The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7
So expected output is 4, 2, 12, 3 and 7
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
We need to check the Horizontal Distances from root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
We can do inorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1.
Following is Java implementation for the same. HashMap is used to store the vertical sums for different horizontal distances. Thanks to Nages for suggesting this method.
import java.util.HashMap;
// Class for a tree node
class TreeNode {
// data members
private int key;
private TreeNode left;
private TreeNode right;
// Accessor methods
public int key() { return key; }
public TreeNode left() { return left; }
public TreeNode right() { return right; }
// Constructor
public TreeNode(int key)
{ this.key = key; left = null; right = null; }
// Methods to set left and right subtrees
public void setLeft(TreeNode left) { this.left = left; }
public void setRight(TreeNode right) { this.right = right; }
}
// Class for a Binary Tree
class Tree {
private TreeNode root;
// Constructors
public Tree() { root = null; }
public Tree(TreeNode n) { root = n; }
// Method to be called by the consumer classes
// like Main class
public void VerticalSumMain() { VerticalSum(root); }
// A wrapper over VerticalSumUtil()
private void VerticalSum(TreeNode root) {
// base case
if (root == null) { return; }
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM =
new HashMap<Integer, Integer>();
// Calls the VerticalSumUtil() to store the
// vertical sum values in hM
VerticalSumUtil(root, 0, hM);
// Prints the values stored by VerticalSumUtil()
if (hM != null) {
System.out.println(hM.entrySet());
}
}
// Traverses the tree in Inoorder form and builds
// a hashMap hM that contains the vertical sum
private void VerticalSumUtil(TreeNode root, int hD,
HashMap<Integer, Integer> hM) {
// base case
if (root == null) { return; }
// Store the values in hM for left subtree
VerticalSumUtil(root.left(), hD - 1, hM);
// Update vertical sum for hD of this node
int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD);
hM.put(hD, prevSum + root.key());
// Store the values in hM for right subtree
VerticalSumUtil(root.right(), hD + 1, hM);
}
}
// Driver class to test the verticalSum methods
public class Main {
public static void main(String[] args) {
/* Create following Binary Tree
1
/
2 3
/ /
4 5 6 7
*/
TreeNode root = new TreeNode(1);
root.setLeft(new TreeNode(2));
root.setRight(new TreeNode(3));
root.left().setLeft(new TreeNode(4));
root.left().setRight(new TreeNode(5));
root.right().setLeft(new TreeNode(6));
root.right().setRight(new TreeNode(7));
Tree t = new Tree(root);
System.out.println("Following are the values of" +
" vertical sums with the positions" +
" of the columns with respect to root ");
t.VerticalSumMain();
}
}
Vertical Sum in Binary Tree | Set 2 (Space Optimized)
Time Complexity: O(n)
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if (root1 == NULL && root2 == NULL)
return true;
if (root1 == NULL || root2 == NULL)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right) );
}
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;
if (T == NULL)
return false;
/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||
isSubtree(T->right, S);
}
/* Helper function that allocates a new node with the given data
and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above function */
int main()
{
// TREE 1
/* Construct the following tree
26
/
10 3
/
4 6 3
30
*/
struct node *T = newNode(26);
T->right = newNode(3);
T->right->right = newNode(3);
T->left = newNode(10);
T->left->left = newNode(4);
T->left->left->right = newNode(30);
T->left->right = newNode(6);
// TREE 2
/* Construct the following tree
10
/
4 6
30
*/
struct node *S = newNode(10);
S->right = newNode(6);
S->left = newNode(4);
S->left->right = newNode(30);
if (isSubtree(T, S))
printf("Tree 2 is subtree of Tree 1");
else
printf("Tree 2 is not a subtree of Tree 1");
getchar();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.