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

typedef struct node* tree;
typedef struct node {
	int key;
	tree left, mid, right;
} node;

void printTree(tree t); // Thank you Toni for putting your code online so I can steal it.



int count(tree t) {
	return !t?0:
	       count(t->left)+count(t->mid)+count(t->right)
	       +
	       !((!!t->left+!!t->mid+!!t->right)%2)
	       ;
	
	// ---
	
	if (t == NULL) return 0;
	
	int numchildren = 0;
	if (t->left != NULL) numchildren++;
	if (t->mid != NULL) numchildren++;
	if (t->right != NULL) numchildren++;
	
	int here = 0;
	if (numchildren == 0 || numchildren == 2)
		here = 1;
	
	return here + count(t->left) + count(t->mid) + count(t->right);
}



int main() {
	node* s = malloc(sizeof(node));
	s->key = 2;
		node* s1 = malloc(sizeof(node));
		s1->key = 3;
		s->left = s1;
			node* s11 = malloc(sizeof(node));
			s11->key = 2;
			s11->left = NULL;
			s11->mid = NULL;
			s11->right = NULL;
			s1->left = s11;
			node* s12 = malloc(sizeof(node));
			s12->key = 4;
			s12->left = NULL;
			s12->mid = NULL;
			s12->right = NULL;
			s1->right = s12;
		node* s2 = malloc(sizeof(node));
		s2->key = 99;
		s2->left = NULL;
		s2->mid = NULL;
		s2->right = NULL;
		s->mid = s2;
		node* s3 = malloc(sizeof(node));
		s3->key = 1;
		s3->left = NULL;
		s3->mid = NULL;
		s3->right = NULL;
		s->right = s3;
	
	printTree(s);
	
	printf("\n%d\n", count(s));
}






// Stolen from http://wwwtcs.inf.tu-dresden.de/~dietze/2014w/aud/
// ... for purely academic reasons!

void printTreeHelper(tree t, int level, unsigned int branches) {
	int i;
	if (level > 0) {
		for (i = 0; i < level - 1; ++i) {
			if (branches & (1 << i)) {
				printf("│ ");
			} else {
				printf("  ");
			}
		}
		if (branches & (1 << i)) {
			printf("├ ");
		} else {
			printf("└ ");
		}
	}
	if (t == NULL) {
		printf("NULL\n");
	} else {
		printf("%i\n", t->key);
		if (t->left || t->right) {
			printTreeHelper(t->left, level + 1, branches | (1 << level));
			printTreeHelper(t->mid, level + 1, branches | (1 << level));
			printTreeHelper(t->right, level + 1, branches);
		}
	}
}

void printTree(tree t) {
	printTreeHelper(t, 0, 0);
}