Can conditional break in a loop be rewritten for easier understanding?

Question

while cond1
    ...
    if cond2
        ...
    else
        ...
        break

The while loop above has two termination conditions,

• cond2 and !cond1
• !cond2

When the commands that are represented by ... are long, I feel the code is not easy to understand. The two termination conditions for the same while-loop are far apart. See when using break is bad.

Is there a better way to write such code for easier to be understood? For example, can we avoid writing the two termination conditions in two separate places?

My question comes from reading a C++ program, but is actually not specific to programming languages. Just assume usual control constructs available in programming languages.

---

A non-recursive implementation of postorder traversal of a binary tree, using stack

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    const TreeNode *p = root, *q = nullptr;
    do {
        while (p != nullptr) { 
            s.push(p);
            p = p->left;
        }
        q = nullptr;

        // start of the example
        while (!s.empty()) {
            p = s.top();
            s.pop();
            if (p->right == q) {
                result.push_back(p->val);
                q = p;  
            } else {
                s.push(p);
                p = p->right;
                break;         //<=== exit inner loop
            }
         }   
        // end of example

    } while (!s.empty());  //end do..while
    return result;
}

Answer 1

The general control flow issue that you expose

The things are not so simple as you present:

while cond1
    ...block1...
    if cond2
        ...block2...
    else
        ...block3...
        break

When cond1 is false at the first iteration, the loop is not executed at all. In all other cases, block1 is executed and it could impact cond2.

Then only, if !cond2 the loop is exited; but only after block3 is executed, being understood that block3 could alter both cond1 and cond2, without changing the fact that the loop is to be exit.

Note also that you could enter the loop, execute block1 and block2 or only block1.

Can it be solved easily without rewriting the different parts ?

One could try to trick by using side effects, coma operator and logical connectors in the conditions:

while (cond1 && (block1 , !cond2) )  // ouch the awful coma operator
    block2  

But this might get very unreadable ! And you still have to find a trick that would make block3 executed only if the loop was executed at least one time, and if the loop failed because of !cond2.

Even with an ADA like loop structure which would allow to have the loop condition in the middle , you could not easily rewrite this, at least for the general case.

You could also try to introduce some boolean indicators, and with some clever starting state and combinations of if and while manage to get all the looping conditions in one place. But try it: it will not look simpler than what you have written initially ! On contrary, the extra tricks will make the whole thing much more difficult to read.

So how to solve it ?

The problem is not really the control flow by itself: it's in fact easy to understand and grasp the special cases.

The real challenge for readability, is when your blocks become to big and eventually too nested.

In this case, follow Uncle Bob's advice: keep the functions small by doing one thing and at one level of abstraction. If it's to big, you're doing too many things. So put the blocks in smaller functions (passing by reference if side effects are required) and give the function names that make your intent clear.

Answer 2

Firstly, you probably should use a recursive algorithm here. The builtin stack will be faster and easier to use then your manually constructed on here. Leaving that aside:

I find a useful technique when attempting to get rid of mid-loop breaks is to temporarily duplicate code to avoid it. Then I try to clean up the resulting code. In your case, I would start by rewriting your code like so:

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    const TreeNode *p = root, *q = nullptr;
    do {
        while (p != nullptr) { 
            s.push(p);
            p = p->left;
        }
        q = nullptr;

        while (!s.empty()) {
            p = s.top();
            s.pop();
            if (p->right == q) {
                result.push_back(p->val);
                q = p;  
            } else {
                s.push(p);
                p = p->right;
                while (p != nullptr) { 
                    s.push(p);
                    p = p->left;
                }
                q = nullptr;
            }
         }   
    } while (!s.empty());  //end do..while
    return result;
}

Having done this, we can see that the outer loop is pointless. It'll never execute because the inner loop now only terminates when the stack is empty. So we can remove it:

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    for(TreeNode *p = root; p != nullptr;p = p->left) { 
        s.push(p);
    }

    TreeNode* q = nullptr;

    while (!s.empty()) {
        TreeNode * p = s.top();
        if (p->right == q) {
            result.push_back(p->val);
            s.pop();
            q = p;  
        } else {
            for(TreeNode *node = p->right; p != nullptr; p = p->left) {
                s.push(node);
            }
            q = nullptr;
        }
     }   

    return result;
}

We can then add some general cleanups: improve the scope of variables, avoiding popping elements from the stack just to push them again, etc.

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> result;
    stack<const TreeNode *> s;

    for(TreeNode *p = root; p != nullptr;p = p->left) { 
        s.push(p);
    }

    TreeNode* q = nullptr;

    while (!s.empty()) {
        TreeNode * p = s.top();
        if (p->right == q) {
            result.push_back(p->val);
            s.pop();
            q = p;  
        } else {
            for(TreeNode *node = p->right; p != nullptr; p = p->left) {
                s.push(node);
            }
            q = nullptr;
        }
     }   

    return result;
}

The result is code that much more clearly conveys what your algorithm is doing. This is a bit of duplication pushing items into left, and it bothers you, you can extract it into a function.