Question

Write a C++ method that traverses through a binary tree (only 2 children to a node) using preorder traversal and finds the proper place to put in a new node. The method will take in an int and traverse through the tree to find the proper place but it must use PREORDER traversal to find a proper position.

struct node{

int data;

struct node* left, *right;

Node(int Data){

this->data=data;

left=right=NULL;

}

};

void preorderAdd(int newNum){

//Method to traverse using preorder and to add in new node.

}

Answer 1

void insert(struct node* temp, int data)

{

    queue<struct node*> q;

    q.push(temp);

    while (!q.empty()) {

        struct node* temp = q.front();

        q.pop();

if (!temp->left) {

            temp->left = newNode(data);

            break;

        } else

            q.push(temp->left);

        if (!temp->right) {

            temp->right = newNode(data);

            break;

        } else

            q.push(temp->right);

    }

}

//For traversing inorder

void inorder(struct node* temp)

{

    if (!temp)

        return;

    inorder(temp->left);

    cout << temp->key << endl;

    inorder(temp->right);

}