Victor
BAN USER#include <stdio.h>
#include <stdlib.h>
typedef struct BST_ {
int data;
struct BST_ *left;
struct BST_ *right;
} BST;
int traverse(BST *t, int x, int y)
{
int found1 = 0;
int found2 = 0;
int found_below1;
int found_below2;
int found_below;
if (t == NULL)
return 0;
if (t->data == x) {
found1 = 1;
}
if (t->data == y) {
found2 = 1;
}
found_below = traverse(t->left, x, y);
found_below |= traverse(t->right, x, y);
found_below1 = found_below & 0xff;
found_below2 = found_below >> 8 & 0xff;
if (found_below1 && found_below2) {
printf("%d ", t->data);
}
int ret = (found2 | found_below2) << 8 |
found1 | found_below1;
return ret;
}
main()
{
BST *x1 = (BST *) malloc(sizeof(BST));
BST *x2 = (BST *) malloc(sizeof(BST));
BST *x3 = (BST *) malloc(sizeof(BST));
BST *x4 = (BST *) malloc(sizeof(BST));
BST *x5 = (BST *) malloc(sizeof(BST));
BST *x6 = (BST *) malloc(sizeof(BST));
BST *x7 = (BST *) malloc(sizeof(BST));
x1->data = 1;
x1->left = x2;
x1->right = x3;
x2->data = 2;
x2->left = x4;
x2->right = x5;
x3->data = 3;
x3->left = x6;
x3->right = x7;
x4->data = 4;
x4->left = NULL;
x4->right = NULL;
x5->data = 5;
x5->left = NULL;
x5->right = NULL;
x6->data = 6;
x6->left = NULL;
x6->right = NULL;
x7->data = 7;
x7->left = NULL;
x7->right = NULL;
traverse(x1, 6, 7);
printf("\n");
free(x1);
free(x2);
free(x3);
free(x4);
free(x5);
free(x6);
free(x7);
}
If you have 2N points, divide them with an imaginary line such that N points lie on one side of the line and N on another (say left half and right half)
- Victor May 24, 2012a) you have N chords joining N points on left half and right half
b) you have N - 1 cords joining points on left half
c) you have N - 1 cords joining points on right half
d) you have N - 1 cords joining one point on left half and one point on right half that is immediately below the chord you drew in a)
So answer is a) + b) + c) + d)
N + N - 1 + N - 1 + N - 1 = 4N - 3