230.c

#include<stdio.h>
#include<stdlib.h>

structTreeNode {
intval;
structTreeNode*left;
structTreeNode*right;
};

/** Modification of Morris in-order tree traversal */
intkthSmallest0(structTreeNode*root, intk) {
if (root==NULL||k==0) return-1;

structTreeNode*cur=root;
structTreeNode**p=NULL;
inti=0;
intans=-1;

while (cur!=NULL) {
if (cur->left!=NULL) {
/* find predecessor node */
p=&(cur->left);
while (1) {
if (*p==NULL) {
if (i >= k) cur=cur->right; /* get to rightest node asap */
else {
*p=cur;
cur=cur->left;
 }
break;
 }

if (*p==cur) {
if (++i==k) ans=cur->val; /* can't just return, have to recover tree */
*p=NULL; /* time complexity changes from O(k) to O(n) */
cur=cur->right;
break;
 }
p=&((*p)->right);
 }
 }
else {
if (++i==k) ans=cur->val;
cur=cur->right;
 }
 }

returnans;
}

/** Divide and conquer, just like quick sort */
intgetCount(structTreeNode*root) {
if (root==NULL) return0;
returngetCount(root->left) +getCount(root->right) +1;
}

intkthSmallest1(structTreeNode*root, intk) {
if (root==NULL||k==0) return-1;

intl=getCount(root->left); /* it takes O(n) */
if (l==k-1) returnroot->val;
if (l<k)
returnkthSmallest1(root->right, k-l-1);
else
returnkthSmallest1(root->left, k);
}

/** In-order traversal */
intfindHelper(structTreeNode*root, int*k) {
if (root==NULL||*k==0) return-1;

intx=findHelper(root->left, k);
if (*k==0) returnx;
 (*k)--;
if (*k==0) returnroot->val;
returnfindHelper(root->right, k);
}

intkthSmallest(structTreeNode*root, intk) {
returnfindHelper(root, &k);
}

intmain() {
structTreeNode*r= (structTreeNode*)calloc(9, sizeof(structTreeNode));
structTreeNode*p=r;

p->val=6;
p->left=r+1;
p->right=r+2;

p=p->left;
p->val=2;
p->left=r+3;
p->right=r+4;

p=p->left;
p->val=1;

p=r+4;
p->val=4;
p->left=r+5;
p->right=r+6;

p=r+5;
p->val=3;

p=r+6;
p->val=5;

p=r+2;
p->val=7;
p->right=r+7;

p=p->right;
p->val=9;
p->left=r+8;

p=p->left;
p->val=8;

inti;
for (i=1; i <= 9; i++) {
printf("%d\n", kthSmallest(r, i));
 }
return0;
}