C2K C2K - 4 months ago 20
C++ Question

Write a function to "unbalance" a binary search tree?

I am trying to write a method for a binary search tree class to unbalance a balanced a normal tree. Below is a representation of what the method should do:

10 1
/ \ \
5 12 ===> 5
/ \ / \ \
1 6 11 15 6

Method should not create new nodes but rather manipulate older nodes to connect them in the correct order to get the final unbalanced tree.

From the order in which the elements are appearing in the unbalanced tree, to me there seems to be some relation between the In Order Traversal (Left, Middle, Right).

Any pseudocode would be appreciated! I have been able to solve the problem for a 3-node tree but cannot understand how to expand my solution to a larger tree. I was trying to think of a recursive solution and a base case but am stuck.

void unbalance (Node* t){
t->left->right = t;
t = t->left;
t->right->left = nullptr;

This function works fine on a tree like:

2 1
/ \ ===> \
1 3 2

void unbalance(Node **pp) {
    Node *p;
    while ((p = *pp)) {
        if (!p->left) {
            pp = &p->right;
        } else {
            Node *tmp = p->left->right;
            *pp = p->left;
            p->left->right = p;
            p->left = tmp;

Node *tree = ...;

This code is based on @templatetypedef's answer. It uses a pointer-to-pointer to avoid orphaning nodes (which also gets rid of finalRoot, whose only purpose is to avoid orphaning the original root passed in by the caller).

The idea is to walk down the tree along the rightmost branch. If there never are any left children, we only enter the first part of the if statement and exit without doing anything.

The else part is used when there is a left subtree. In that case we rotate the tree right. animated tree rotation

This has the effect of pulling one node up from the left subtree, i.e. our left subtree is now one node smaller. We repeat this until the left subtree is completely gone, at which point we enter the first part of the if again. Then we go down to the remaining right subtree and repeat the whole thing.