Question

In: Computer Science

Write a boolean function that is given a binary tree and returns true if and only...

Write a boolean function that is given a binary tree and returns true if and only if the tree has an odd number of nodes. An empty tree is considered to have an even number of nodes. Notes: The function should have just one argument, a pointer to the root. No global variables may be used. No additional functions may be defined. You may not count the number of nodes.

Solutions

Expert Solution

BOOLEAN FUNCTION :

bool OddCheck(BinaryTreeNode<int>* root){
  
// if the binary tree is Empty ie. considered as even nodes.
if(root==NULL)
return false;
  
// if binary tree only contains one node ie.odd number f nodes
if(root->left==NULL&&root->right==NULL)
return true;
  
  
//if binary tree have only contains right subtree and left subtree is Empty.
else if(root->left==NULL&&root->right!=NULL){
bool a = OddCheck(root->right);
if(a==true)
return false;
else
return true;
  
}
  
//if binary tree have only contains left subtree and right subtree is Empty.
else if(root->left!=NULL&&root->right==NULL){
  
bool a = OddCheck(root->left);
if(a==true)
return false;
else
return true;
  
}
  
  
// If both Left Subtree and Right Subtree is not Empty.
else if(root->left!=NULL&&root->right!=NULL){
  
bool a = OddCheck(root->left);
bool b = OddCheck(root->right);
  
//if both subtrees have odd numbers of nodes. Then result will be odd.
if(a==true&&b==true)
return true;
  
//If both subtrees have even number of nodes then result will be:

// even + even + 1(for root) =ODD


else if(a==false&&b==false)
return true;
  
//for all other cases the result will be even numbers of nodes.
else
return false;
  
  
}
  
}


Related Solutions

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the...
(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the nodes in a binary tree that have only one child. Convert it to an iterative version. in C++
PYTHON: Write a function named is_palindrome() that returns boolean True if a word or phrase is...
PYTHON: Write a function named is_palindrome() that returns boolean True if a word or phrase is a palindrome, and boolean False if it is not. The palindromes for this problem are contained in the list below. You must use this list in your solution. Use a for loop to retrieve each palindrome and test it. Your script should test each string in the list of palindromes below. Be aware there's a second list of palindromes embedded in the palindromes list....
Write function boolean isSorted(int a[], int size). The function returns true if array a is sorted...
Write function boolean isSorted(int a[], int size). The function returns true if array a is sorted in either ascend order or descend order; false otherwise. c++
Implement a function that returns all the items in a binary search tree in order inside...
Implement a function that returns all the items in a binary search tree in order inside a std::vector. Use the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; std::vector<int> inorder_traversal(BTNode *node) { // implement } If the BST has no values, return a vector with no items in it. #include <iostream> #include <vector> class BTNode { public: int item; BTNode *left; BTNode...
Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree...
Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree in level-order. That is, the method should return the root, then the nodes at depth 1, followed by the nodes at depth 2, and so on. Your algorithm should begin by putting the tree root on an initially empty queue. Then dequeue a node, add it to the output, and enqueue its left and right children (if they exist). Repeat until the queue is...
Write an evenTest(n) function that returns True if it is given an even integer and False...
Write an evenTest(n) function that returns True if it is given an even integer and False if it is given an odd number. The rest of your code (outside of the function) should get an integer number from the user, call evenTest(n) to test if the number is even, and then tell the user if the number was even or odd. Name the program even_or_odd.py. Part 2. Salary.py (5 pts) You are offered two options to receive salary: • Option...
Write a function matrix_power(A, n) that computes the power An using Boolean arithmetic and returns the...
Write a function matrix_power(A, n) that computes the power An using Boolean arithmetic and returns the result. You may assume that A is a 2D list containing only 0s and 1s, A is square (same number of rows and columns), and n is an integer ≥ 1. You should call your previously written matrix multiply boolean function. Example: Let R = [ [0, 0, 0, 1], [0, 1, 1, 0], [0, 0, 0, 1], [0, 0, 1, 0] ] Then...
Write a function named mirror_tree that accepts a pointer to the root of a binary tree...
Write a function named mirror_tree that accepts a pointer to the root of a binary tree of integers. Your function should rearrange the nodes into a mirror tree of the original tree. The mirror tree has the left and right subtrees reversed for each node. Constraints: You must implement your function recursively and without using loops. Do not construct any new BST objects in solving this problem (though you may create as many NODE* pointer variables as you like). Do...
write a function that takes as input the root of a general tree and returns a...
write a function that takes as input the root of a general tree and returns a binary tree generated by the conversion process illustrated in java
CODE IN JAVA** I(a). Given a pointer to the root of a binary tree write a...
CODE IN JAVA** I(a). Given a pointer to the root of a binary tree write a routine that will mark (use a negative number like -999 for the info field) every node in the tree that currently has only a left son. You can assume the root of the tree has both a right and left son. When finished tell me how many nodes had only a left son as well as how many nodes are in the tree in...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT