CareerCup4.6.cpp

CareerCup4.6.cpp

/*
 Chapter 4
 
 4.6  Write an algorithm to find the 'next' node (i.e., in-order successor)
 of a given nodes in a binaru search tree. You may assume that each node
 has a link to its parent.
 */

#include <iostream>

using namespace std;

typedef struct tNode {
    int value;
    struct tNode* left;
    struct tNode* right;
    struct tNode* parent;
}tNode;

tNode* newNode(int v)
{
    tNode* node = new tNode;
    node->value = v;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}

// Function to find the 'next' node
tNode* nextNode(tNode* pre)
{
    // Declare next node
    tNode* next = NULL;
    // Case1: pre has right subtree
    // next node is the leftmost node of right subtree
    if (pre->right) {
        next = pre->right;
        while (next->left) {
            next = next->left;
        }
    }
    // Case 2: pre has no right subtree, pre <= parent
    // next node must be its parent if exist
    else if (pre->parent && pre->value <= pre->parent->value)
        next = pre->parent;
    // Case 3: pre has no right subtree, pre > parent
    // search bottom up to root
    else if ( pre->parent && pre->value > pre->parent->value) {
        tNode* p = pre->parent;
        while (p->parent) {
            if (pre->value <= p->parent->value)
                next = p->parent;
            p = p->parent;
        }
    }
    return next;
}
// Main Function to test
int main()
{
    /*      5
          /   \
        3      10
       / \    /
      1   4  7      */
    tNode* root = newNode(5);
    tNode* a = newNode(1);
    tNode* b = newNode(3);
    tNode* c = newNode(4);
    tNode* d = newNode(10);
    tNode* e = newNode(7);
    root->left = b; root->right = d;
    b->parent = root; d->parent = root;
    b->left = a; b->right = c;
    a->parent = b; c->parent = b;
    d->left = e; e->parent = d;
    // find 'next' node
    tNode* next = nextNode(root);
    if (next)
        cout << "The next node is: " << next->value << endl;
    else
        cout << "Not found. This is the last node." << endl;
    return 0;
}