3
\$\begingroup\$

How can I optimize this code?

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

struct Node
{
    int data;
    Node *left,*right;
};

Node *createNode(int data){
    Node *node=new Node;
    node->left=NULL;
    node->right=NULL;
    node->data=data;
    return node;
}

Node buildTree(Node *newNode,queue<Node *>&q){
    Node *f=q.front();
    if(f->left && f->right) {q.pop();f=q.front();}
    if(!f->left) f->left=newNode;
    else if(!f->right) f->right=newNode;
    q.push(newNode);
}


void levelOrder(Node *root){
    queue<Node*>q;
    if(root){
        q.push(root);
        while(!q.empty()){
            Node *d =q.front();
            q.pop();
            cout<<d->data<<" ";
            if(d->left) q.push(d->left);
            if(d->right) q.push(d->right);
        }
    }
}

int main(){
    Node *root=createNode(10);
    queue<Node *>q;
    q.push(root);
    for(int i=0;i<10;i++){
        buildTree(createNode(i),q);
    }
    levelOrder(root);
    return 0;
}
\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

using namespace std;

using namespace std;

Why is “using namespace std;” considered bad practice?

The particular problem I have with it here is that it obscures that you are using std::queue and not some custom class.

Note that this can also cause problems if you later convert it to header file, which would be natural for a general use data structure.

Don't go the long way around

Node *createNode(int data){
    Node *node=new Node;
    node->left=NULL;
    node->right=NULL;
    node->data=data;
    return node;
}

Rather than create a function for this, consider just creating a constructor for struct Node.

Node::Node(int datum) {
    this->datum = datum;
    left = NULL;
    right = NULL;
}

Note that datum is the singular form of data, so I changed the field in Node to datum as it only holds one piece.

        buildTree(createNode(i),q);

could become

        buildTree(new Node(i), q);

This calls a constructor directly rather than creating a function just to call the default constructor and set the data.

Why wait?

    if(f->left && f->right) {q.pop();f=q.front();}
    if(!f->left) f->left=newNode;
    else if(!f->right) f->right=newNode;

This could be

    if (f->left) {
        f->right = newNode;
        q.pop();
    } else {
        f->left = newNode;
    }

This works because you know that something is only in the queue until both its children are added. Then it is removed. So you don't need to check for the both children full case if you only ever add to the tree with this method.

I changed the order because I find it easier to read positive conditions with else blocks. An else is essentially the negation of the if. This way we aren't negating a negative.

What if something else adds to the tree? That would be problematic. Of course, that was already true. Something else adding to the tree would interfere with the order that you use the queue to enforce.

Removals are also problematic with either implementation.

This is why Node would normally be a hidden data type, not exposed to callers. Then you could be sure that only your tree class would be able to access it.

Don't make data structures that you don't use

    queue<Node*>q;
    if(root){

If you do this in the other order, you can save the overhead of creating the std::queue.

    if (root) {
        queue<Node*> q;

or even

    if (!root) {
        return;
    }

    queue<Node*> q;

Which also reduces the indent.

Efficiency

The biggest problem with efficiency that I see is that this doesn't seem to be a tree in any meaningful sense. Sure, the data structure behind it is a tree, but the operations aren't. You buildTree in insertion order. Then you levelOrder to read back the tree in insertion order. If you only wanted to do that, then a std::vector would be a much more efficient data structure. You wouldn't need the std::queue to manage the insertions nor reading them back.

    Node *root=createNode(10);
    queue<Node *>q;
    q.push(root);
    for(int i=0;i<10;i++){
        buildTree(createNode(i),q);
    }
    levelOrder(root);

would become

    std::vector<int> data;
    data.push_back(10);
    for (int i = 0; i < 10; i++) {
        data.push_back(i);
    }

    for (auto datum : data) {
        std::cout << datum << " ";
    }

Isn't that simpler? No new functions required. Also, rather than using a pointer-based data structure and a queue, this just uses one array-based data structure. You could also use a std::queue instead of a std::vector.

Encapsulation

This is also encapsulated better. Instead of having to create a tree structure and a queue in order to call buildTree, this simply calls push_back and lets std::vector handle the details internally. Consider the following interface

class InsertionOrderTree {
    struct Node {
        int datum;
        Node *left;
        Node *right;
    };

    Node *root;
    std::queue<int> q;

    public:
    InsertionOrderTree();
    build(int datum);
    traverse();
};

InsertionOrderTree::InsertionOrderTree() {
    root = NULL;
}

This hides the implementation detail of using a queue from any callers. Callers shouldn't have to know how you do things, just what you promise to do. They certainly should not have to create a specific data structure just to help you do whatever it is that you are doing. You should create your own data structures if you need them.

Note that the implementations of build and traverse would change from your original versions. In particular, build needs to handle a NULL root.

Unsolicited advice

This is a bad use case for a tree though. You should probably either find a different use case that better fits a tree (if you just want to implement a tree) or use a different data structure (if this is really the problem that you need to solve).

\$\endgroup\$
2
\$\begingroup\$

I am still learning myself, but I will only give you advice that I have been given recently.

Instead of using the new operator try researching smart pointers, std::unique_ptr, it takes away the pain of handling the memory manually, especially if you are coming for languages like Java, C# or PHP(Like me), where you are not used to memory management.

\$\endgroup\$
1
\$\begingroup\$

I see some things that may help you improve your code.

Make sure all paths return a value

The buildTree routine claims to return a Node but doesn't. Either change the function signature to void or modify the code to actually return a Node.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Use object orientation

Because you're writing in C++, it would make sense to have methods that operate on a class such as Node be member functions rather than separate functions. In addition, it allows the implementation to be separate from the interface. This allows others to use your code without needing to know or care about the details of how it's implemented. An example is that the buildTree() function very peculiarly requires a std::queue as a passed value. Better would be to have a Tree object and then have a levelOrder traversal member fuction.

Use a constructor rather than a standalone function

The createNode function would be better expressed as Node constructor.

struct Node {
    Node(int thedata) 
        : data{thedata}, left{nullptr}, right{nullptr}
    {}
    int data;
    Node *left, *right;
};

Now instead of using createNode, you can simply do this:

Node *root = new Node(10);

Use more whitespace

Instead of writing a line like this:

if(f->left && f->right) {q.pop();f=q.front();}

use a bit more whitespace and write it like this:

if (f->left && f->right) {
    q.pop();
    f = q.front();
}

Don't leak memory

Unless there is a corresponding delete for every new in your program, it will leak memory. One simple way to do this with the existing code would be to do a post-order traversal like this:

void delTree(Node *root) {
    if (root) {
        delTree(root->left);
        delTree(root->right);
        delete root;
        root = nullptr;
    }
}

Consider an alternative data structure

Depending on how you're going to be using these binary trees, an alternative structure would be to use an array. The canonical way to do this would be to store the root at index 1. Then the left and right children of the root would be at index 2 and index 3 respectively. Generally, then for any given node stored at index \$n\$, its left and right children are at index \$2n\$ and \$2n+1\$ respectively. This makes an level traversal extremely simple since all that's then needed is to step through the array.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.