In-order successor

Find the next in-order successor of a binary tree node.  Assume that each node maintains a pointer to its parent.
/*
 * NextNodeInOrderSuccession.cpp
 *
 *  Created on: May 05, 2012
 *      Author: Kiran Hegde
 */


#include <iostream>
#include <queue>
#include <string>

using namespace std;

class BinaryTreeNode {
public :
    BinaryTreeNode(int d) : left(NULL), right(NULL), parent(NULL), data(d) {}

    ~BinaryTreeNode() {
        if (left != NULL) {
            delete left;
            left = NULL;
        }
        if (right != NULL) {
            delete right;
            right = NULL;
        }
    }

    void setLeftChild(BinaryTreeNode *node) {
        left = node;
        left->parent = this;
    }

    void setRightChild(BinaryTreeNode *node) {
        right = node;
        right->parent = this;
    }

    BinaryTreeNode *left;
    BinaryTreeNode *right;
    BinaryTreeNode *parent;
    int data;
};

/**
 *
 */
void printTree(BinaryTreeNode *root) {
    if (root == NULL){
        return;
    }
    queue<BinaryTreeNode *> treeQueue;
    queue<int> levelQueue;
    queue<string> rightLeftFlagQueue;

    treeQueue.push(root);
    levelQueue.push(0);
    rightLeftFlagQueue.push("Top");

    cout << "Level 1: ";

    int prevLevel = 0;
    while(! treeQueue.empty()) {
        BinaryTreeNode *node = treeQueue.front();
        int level = levelQueue.front();
        if (node != NULL) {
            if (level > prevLevel) {
                prevLevel = level;
                cout << endl;
                cout << "Level " << level + 1 << ": ";
            }
            string rightLeftFlag = rightLeftFlagQueue.front();
            if (level > 0) {
                cout << node->parent->data << "-->" ;
            }
            cout << node->data << " ";
            if (level > 0) {
                cout << rightLeftFlag << "  ";
            }
            if (node->left != NULL) {
                treeQueue.push(node->left);
                levelQueue.push(level + 1);
                rightLeftFlagQueue.push("L");
            }
            if (node->right != NULL) {
                treeQueue.push(node->right);
                levelQueue.push(level + 1);
                rightLeftFlagQueue.push("R");
            }
        }
        treeQueue.pop();
        levelQueue.pop();
        rightLeftFlagQueue.pop();
    }
}

/**
 * Given a binary tree node, returns the next in-order successor node
 */
BinaryTreeNode *getInOrderSuccessor(BinaryTreeNode *node) {
    if (node == NULL)
        return NULL;

    //If the node is the root or if it has a right sub-tree
    if ((node->parent == NULL) || (node->right != NULL)) {
        //return the leftmost child of right sub-tree
        BinaryTreeNode *n = node->right;
        while (n->left != NULL) {
            n = n->left;
        }
        return n;
    }
    //If the node does not have right children, the next node should be upwards
    //If the is a left child, return the parent
    //If the node is a right child, the parent has already been visited, therefore
    // go up further till a left child is found.  Return the parent node.
    else {
        BinaryTreeNode *n = node;
        BinaryTreeNode *p = node->parent;
        if (p != NULL && p->left != n) {
            n = p;
            p = p->parent;
        }
        return p;
    }

    return NULL;
}

/**
 * Test the code
 */
int main() {
    BinaryTreeNode *n0 = new BinaryTreeNode(0);
    BinaryTreeNode *n1 = new BinaryTreeNode(1);
    BinaryTreeNode *n2 = new BinaryTreeNode(2);
    BinaryTreeNode *n3 = new BinaryTreeNode(3);
    BinaryTreeNode *n4 = new BinaryTreeNode(4);
    BinaryTreeNode *n5 = new BinaryTreeNode(5);
    BinaryTreeNode *n6 = new BinaryTreeNode(6);

    n0->setLeftChild(n1);
    n0->setRightChild(n2);
    n1->setRightChild(n3);
    n3->setLeftChild(n4);
    n4->setLeftChild(n5);
    n4->setRightChild(n6);

    printTree(n0);

    BinaryTreeNode *nextNode = getInOrderSuccessor(n4);
    cout << endl << endl << "In-order successor of 4 is: " << nextNode->data << endl;

    nextNode = getInOrderSuccessor(n3);
    cout << endl << "In-order successor of 3 is: " << nextNode->data << endl;

    delete(n0);
}
Comments