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);
}