Wednesday, July 2, 2008

How to traverse to next sorted element in a binary tree?

#include <iostream>

using namespace std;

template <typename T>
class Node {
public:
Node* left;
Node* right;
T data;
Node(T data) : data(data), left(NULL), right(NULL) {}
Node(T data, Node* left, Node* right) : data(data), left(left), right(right) {}
};

template <typename T>
T traverseNext(Node<T>* n) {
Node<T>* itr = NULL;
if (n->right) {
itr = n->right;
while (itr->left) {
itr = itr->left;
}
}
return itr ? itr->data : NULL;
}

int main() {
Node<int> n6(6);
cout << traverseNext(&n6) << endl; //0

Node<int> n9(9), n11(11);
Node<int> n10(10, &n9, &n11);
Node<int> n14(14);
Node<int> n12(12, &n10, &n14);
n6.right = &n12;
cout << traverseNext(&n6) << endl; //9
cout << traverseNext(&n12) << endl; //14
cout << traverseNext(&n10) << endl; //11
}

No comments: