Apple Interview Question
SDE1sCountry: United States
Doing an inorder traversal will iterate through the nodes in ascending order, but the iterating must be done in steps, which makes it so you can't use a standard recursive inorder DFS traversal. So instead find the leftmost child of the current node and maintain a stack of "found but not processed" nodes. For the next node, pop the next node off the stack, then find the leftmost child of its right child (since you would have already processed its left child), again putting all encountered nodes on the stack.
#include <iostream>
using namespace std;
class node{
public:
int key;
node* left;
node* right;
node(int key) {
this->key = key;
left = right = 0;
}
};
class Tree{
node* root;
public:
Tree(node *p):root(p) {}
void addNode(int key) {
node *p = new node(key);
addNode(p);
}
void addNode(node *p) {
node* curr = root;
node *prev = 0;
while(curr) {
if (curr->key == p->key) {
cout<<"Duplicate key "<<p->key<<endl;
return;
}
prev = curr;
if (curr->key < p->key) {
curr = curr->right;
} else {
curr = curr->left;
}
}
if (prev && prev->key < p->key) prev->right = p; else prev->left = p;
}
node* find(int key) {
node* curr = root;
while(curr) {
if (curr->key == key) {
return curr;
}
if (curr->key < key) {
curr = curr->right;
} else {
curr = curr->left;
}
}
return NULL;
}
~Tree() {
deleteTree(root);
}
void deleteTree(node *p) { //Deletion using Post Order traversal
if (!p) return;
deleteTree(p->left);
deleteTree(p->right);
// cout<<"Deleting "<<p->key<<endl;
delete p;
}
class iterator{
Tree *t;
node *itrPtr;
public:
iterator(Tree *t, node *p):t(t),itrPtr(p) {}
void operator ++(int) {
if (itrPtr->right) {//Go one right, then left all the way to bottom
itrPtr = itrPtr->right;
for(;itrPtr->left;itrPtr=itrPtr->left);
} else {//successor will be the "nearest" ancestor to itrPtr such that itrPtr is in the left subtree of successor
node *curr = t->root,*successor = 0;
while(curr) {
if (curr->key == itrPtr->key) {
itrPtr = successor;
return;
}
if (curr->key < itrPtr->key) {
curr = curr->right;
} else {
successor = curr;
curr = curr->left;
}
}
}
}
node *operator *() {
return itrPtr;
}
bool operator !=(iterator itr) {
if (itrPtr != itr.itrPtr) return true; else return false;
}
};
Tree::iterator begin() {
node *p;
for(p=root;p->left;p=p->left);
return Tree::iterator(this,p);
}
Tree::iterator end() {
return Tree::iterator(this,NULL);
}
};
int main() {
Tree t(new node(100));
t.addNode(50);
t.addNode(25);
t.addNode(10);
t.addNode(40);
t.addNode(30);
t.addNode(45);
t.addNode(75);
t.addNode(65);
t.addNode(90);
t.addNode(95);
t.addNode(80);
t.addNode(77);
t.addNode(150);
t.addNode(130);
t.addNode(110);
t.addNode(120);
t.addNode(170);
t.addNode(160);
for(Tree::iterator itr = t.begin();itr != t.end();itr++) {
static int ctr=0;
ctr++;
cout<<"node-"<<ctr<<": "<<(*itr)->key<<endl;
}
}
- jakob February 02, 2014