Hope you can help me solve the third question it askes?Thank you? Consider the f

Question

Hope you can help me solve the third question it askes?Thank you? Consider the following class for representing a binary tree. class BTNode {int data; BTNode left, right; ... bool isBST() {...} void levelOrder() {...} void toList (List a) (...) Complete the method is BST() which checks if the tree is a BST or not. Boolean isBST () {} Complete the method levelOrder () which traverses the tree in level order and print the data. Use deque class if necessary. void levelOrder () {} Assume that the given tree is a BST. Complete the method to List (List a) which converts the tree to a List a in an ascending order. void toList (list a) {

Explanation / Answer

#ifndef BINARYTREE_H #define BINARYTREE_H #include #include #include #include #include #include "Node.h" template class BinaryTree { public: explicit BinaryTree() : root_(nullptr) { } explicit BinaryTree(std::initializer_list il); BinaryTree(std::initializer_list inList, std::initializer_list preList); ~BinaryTree() = default; std::vector inorder() const; std::vector inorderWithoutRecursion() const; std::vector inorderMorris(); std::vector postorder() const; std::vector preorder() const; void displayLevelOrder() const; void spiralOrder() const; void displayPretty() const; void displayAllPaths() const; size_t size() const; size_t height() const; size_t width() const; size_t leafCount() const; bool isBST() const; bool isSumProperty() const; void toSumProperty(); bool isBalanced() const; void mirror(); void toList(); // Lowest Common Ancestor std::shared_ptr lca(const T& data1, const T& data2) const; bool isSubTree(const BinaryTree& sub); bool isSubTree(const std::shared_ptr& sub, const std::shared_ptr& org); // TODO: implement == bool identical(const std::shared_ptr& sub, const std::shared_ptr& org); private: void insert(const T& data); std::shared_ptr createBT(typename std::initializer_list::iterator inStart, typename std::initializer_list::iterator inEnd, typename std::initializer_list::iterator& preStart); void inorder(std::shared_ptr root, std::vector& v) const; void postorder(std::shared_ptr root, std::vector& v) const; void preorder(std::shared_ptr root, std::vector& v) const; void levelorder(std::queue& q) const; void displayPretty(std::queue& q) const; void displayAllPaths(std::shared_ptr root, std::vector v) const; size_t size(std::shared_ptr root) const; size_t height(std::shared_ptr root) const; size_t width(std::shared_ptr root) const; size_t leafCount(std::shared_ptr root) const; bool isBST(std::shared_ptr root, T min, T max) const; bool isSumProperty(std::shared_ptr root) const; void increment(std::shared_ptr root, const T& diff); void toSumProperty(std::shared_ptr root); bool isBalanced(std::shared_ptr root, size_t& height) const; void mirror(std::shared_ptr root); void join(std::shared_ptr a, std::shared_ptr b); std::shared_ptr append(std::shared_ptr a, std::shared_ptr b); std::shared_ptr toList(std::shared_ptr root); virtual std::shared_ptr lca(std::shared_ptr root, const T& data1, const T& data2) const; protected: std::shared_ptr root_; }; template BinaryTree::BinaryTree(std::initializer_list il) { for (const auto& data : il) { insert(data); } } template BinaryTree::BinaryTree(std::initializer_list inList, std::initializer_list preList) { typename std::initializer_list::iterator preStart = preList.begin(); root_ = createBT(inList.begin(), inList.end(), preStart); } template std::shared_ptr BinaryTree::createBT(typename std::initializer_list::iterator inStart, typename std::initializer_list::iterator inEnd, typename std::initializer_list::iterator& preStart) { // Nothing in the inorder list. if (inStart == inEnd) return nullptr; std::shared_ptr temp = std::make_shared(*preStart++); // Only 1 element in the inorder list. It does not have any child. if (inStart + 1 == inEnd) return temp; auto it = std::find(inStart, inEnd, temp->data); temp->left = createBT(inStart, it, preStart); temp->right = createBT(it + 1, inEnd, preStart); return temp; } template std::vector BinaryTree::inorder() const { std::vector v; inorder(root_, v); return v; } template std::vector BinaryTree::inorderWithoutRecursion() const { std::vector v; std::stack s; bool done = false; std::shared_ptr current = root_; while (!done) { if (current) { s.push(current); current = current->left; } else { if (s.empty()) done = true; else { current = s.top(); s.pop(); v.push_back(current->data); current = current->right; } } } return v; } template std::vector BinaryTree::inorderMorris() { std::vector v; std::shared_ptr current = root_; while (current) { if (!current->left) { v.push_back(current->data); current = current->right; } else { std::shared_ptr temp = current->left; while (temp->right && temp->right != current) temp = temp->right; if (!temp->right) { temp->right = current; current = current->left; } else { temp->right = nullptr; v.push_back(current->data); current = current->right; } } } return v; } template std::vector BinaryTree::postorder() const { std::vector v; postorder(root_, v); return v; } template std::vector BinaryTree::preorder() const { std::vector v; preorder(root_, v); return v; } template void BinaryTree::displayLevelOrder() const { std::queue q; q.push(root_); q.push(nullptr); levelorder(q); } template void BinaryTree::spiralOrder() const { if (!root_) return; std::stack s1; std::stack s2; s1.push(root_); while (!s1.empty() || !s2.empty()) { while (!s1.empty()) { std::shared_ptr temp = s1.top(); s1.pop(); std::cout right); if (temp->left) s2.push(temp->left); } std::cout right); } std::cout left) { temp->left = std::make_shared(data); break; } else { q.push(temp->left); } if (!temp->right) { temp->right = std::make_shared(data); break; } else { q.push(temp->right); } } } } template void BinaryTree::inorder(std::shared_ptr root, std::vector& v) const { if (root != nullptr) { inorder(root->left, v); v.push_back(root->data); inorder(root->right, v); } } template void BinaryTree::postorder(std::shared_ptr root, std::vector& v) const { if (root != nullptr) { postorder(root->left, v); postorder(root->right, v); v.push_back(root->data); } } template void BinaryTree::preorder(std::shared_ptr root, std::vector& v) const { if (root != nullptr) { v.push_back(root->data); preorder(root->left, v); preorder(root->right, v); } } template void BinaryTree::levelorder(std::queue& q) const { while (!q.empty()) { std::shared_ptr temp = q.front(); q.pop(); if (temp) { std::cout left); } if (temp->right) { q.push(temp->right); } if (!q.front()) { q.pop(); std::cout left); size_t rightWidth = width(root->right); return std::max(1 + leftHeight + rightHeight, std::max(leftWidth, rightWidth)); } template size_t BinaryTree::leafCount(std::shared_ptr root) const { if (!root) return 0; if (root->left == nullptr && root->right == nullptr) return 1; return leafCount(root->left) + leafCount(root->right); } template bool BinaryTree::isBST(std::shared_ptr root, T min, T max) const { if (!root) return true; if (root->data data > max) return false; return isBST(root->left, min, root->data - 1) && isBST(root->right, root->data + 1, max); } template bool BinaryTree::isSumProperty(std::shared_ptr root) const { if (!root) return true; if (!root->left && !root->right) return true; T leftValue = {}; T rightValue = {}; if (root->left) leftValue = root->left->data; if (root->right) rightValue = root->right->data; return (root->data == leftValue + rightValue) && isSumProperty(root->left) && isSumProperty(root->right); } template void BinaryTree::increment(std::shared_ptr root, const T& diff) { if (!root) return; root->data += diff; if (root->left) increment(root->left, diff); else increment(root->right, diff); } template void BinaryTree::toSumProperty(std::shared_ptr root) { if (!root) return; if (!root->left && !root->right) return; toSumProperty(root->left); toSumProperty(root->right); T leftValue = {}; T rightValue = {}; if (root->left) leftValue = root->left->data; if (root->right) rightValue = root->right->data; T diff = root->data - (leftValue + rightValue); if (!diff) return; if (diff < 0) root->data += -diff; if (diff > 0) increment(root->left, diff); } template bool BinaryTree::isBalanced(std::shared_ptr root, size_t& height) const { if (!root) { height = 0; return true; } size_t leftHeight; size_t rightHeight; bool isLeftBalanced = isBalanced(root->left, leftHeight); bool isRightBalanced = isBalanced(root->right, rightHeight); height = std::max(leftHeight, rightHeight) + 1; return (std::abs(leftHeight - rightHeight) < 2) && isLeftBalanced && isRightBalanced; } template void BinaryTree::mirror(std::shared_ptr root) { // 3 parts of recursion: // 1. termination condition if (!root) return; // step 3 can be done before step 2. // 2. recursion call mirror(root->left); mirror(root->right); // 3. some task to perform std::shared_ptr temp = root->right; root->right = root->left; root->left = temp; } template void BinaryTree::join(std::shared_ptr a, std::shared_ptr b) { a->right = b; b->left = a; } template std::shared_ptr BinaryTree::append(std::shared_ptr a, std::shared_ptr b) { if (!a) return b; if (!b) return a; std::shared_ptr aLast = a->left; std::shared_ptr bLast = b->left; join(aLast, b); join(bLast, a); return a; } template std::shared_ptr BinaryTree::toList(std::shared_ptr root) { if (!root) { return nullptr; } std::shared_ptr aList = toList(root->left); std::shared_ptr bList = toList(root->right); root->left = root; root->right = root; std::shared_ptr temp1 = append(aList, root); std::shared_ptr temp2 = append(temp1, bList); return temp2; } template std::shared_ptr BinaryTree::lca(std::shared_ptr root, const T& data1, const T& data2) const { if (!root) { return nullptr; } if (root->data == data1 || root->data == data2) { return root; } std::shared_ptr lca1 = lca(root->left, data1, data2); std::shared_ptr lca2 = lca(root->right, data1, data2); if (lca1 && lca2) { return root; } return lca1 ? lca1 : lca2; } template bool BinaryTree::isSubTree(const BinaryTree& sub) { return isSubTree(sub.root_, root_); } template bool BinaryTree::isSubTree(const std::shared_ptr& sub, const std::shared_ptr& org) { if (!sub) return true; if (!org) return false; if (identical(sub, org)) return true; return isSubTree(sub, org->left) || isSubTree(sub, org->right); } template bool BinaryTree::identical(const std::shared_ptr& sub, const std::shared_ptr& org) { if (!sub && !org) return true; if (!sub || !org) return false; return sub->data == org->data && identical(sub->left, org->left) && identical(sub->right, org->right); } #endif

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.