struct BinaryTreeNode { int data; BinaryTreeNode* left_child; BinaryTreeNode* ri

ID: 675353 • Letter: S

Question

struct BinaryTreeNode {
int data;
BinaryTreeNode* left_child;
BinaryTreeNode* right_child;
};

class BinaryTree {
public:
BinaryTree();
int Size();
bool Contains(int value);
bool Insert(int value);
bool Remove(int value);
void Clear();

std::string ToString();

BinaryTreeNode* head;
};

Given the ".h" file how could you solve the following problem (C++);

bool ContainsRecursive(const BinaryTreeNode* tree_node, int value) {
return false;
}

// Insert a value into a tree in any position except as the first item. I had a if (head == nullptr) case in my method for that case.This helper then would recursively find where the node needed to go, then inset it there. Keep in mind that because we aren't self-balancing these trees, you only inset into a 'leaf' node, that is, a node with no children. Because balancing a binary tree is a LOT of work, you can just leave it unbalanced, as long as it's a valid binary search tree.

Explanation / Answer

#include <iostream>
#include <string>
#include <queue>
using namespace std;

// Linked list node
struct ListNode
{
    int data;
    ListNode* next;
};

// Binary tree node structure
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

// Function to insert a node at the beginning of the Linked List
void push(struct ListNode** head_ref, int new_data)
{
    // allocate node and assign data
    struct ListNode* new_node = new ListNode;
    new_node->data = new_data;

    // link the old list off the new node
    new_node->next = (*head_ref);

    // move the head to point to the new node
    (*head_ref)    = new_node;
}

// method to create a new binary tree node from the given data
BinaryTreeNode* newBinaryTreeNode(int data)
{
    BinaryTreeNode *temp = new BinaryTreeNode;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// converts a given linked list representing a complete binary tree into the
// linked representation of binary tree.
void convertList2Binary(ListNode *head, BinaryTreeNode* &root)
{
    // queue to store the parent nodes
    queue<BinaryTreeNode *> q;

    // Base Case
    if (head == NULL)
    {
        root = NULL; // Note that root is passed by reference
        return;
    }

    root = newBinaryTreeNode(head->data);
    q.push(root);
    head = head->next;
    while (head)
    {
        BinaryTreeNode* parent = q.front();
        q.pop();
        BinaryTreeNode *leftChild = NULL, *rightChild = NULL;
        leftChild = newBinaryTreeNode(head->data);
        q.push(leftChild);
        head = head->next;
        if (head)
        {
            rightChild = newBinaryTreeNode(head->data);
            q.push(rightChild);
            head = head->next;
        }

        parent->left = leftChild;
        parent->right = rightChild;
    }
}

void inorderTraversal(BinaryTreeNode* root)
{
    if (root)
    {
        inorderTraversal( root->left );
        cout << root->data << " ";
        inorderTraversal( root->right );
    }
}

int main()
{

    struct ListNode* head = NULL;
    push(&head);
    BinaryTreeNode *root;
    convertList2Binary(head, root);

    cout << "constructed Binary Tree is: ";
    inorderTraversal(root);
    return 0;
}

Navigate

struct Address{ unsigned number; string street; string suffix; string city; stri

struct DoubleLinkedNode { int data; DoubleLinkedNode * prev; DoubleLinkedNode *

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

struct BinaryTreeNode { int data; BinaryTreeNode* left_child; BinaryTreeNode* ri

Question

Explanation / Answer

Related Questions

Navigate