# Counting nodes in a binary tree recursively

## Introduction

The recursive structure of a binary tree makes it easy to count nodes recursively. There are 3 things we can count:

• The total number of nodes
• The number of leaf nodes
• The number of internal nodes

## Counting all nodes

The number of nodes in a binary tree is the number of nodes in the root’s left subtree, plus the number of nodes in its right subtree, plus one (for the root itself).

This lends itself to a simple recursive algorithm for counting the nodes in a binary tree.

unsigned int binarytree_count_recursive(const btnode *root)
{
unsigned int count = 1;
if (root->left != NULL) {
count += binarytree_count_recursive(root->left);
}
if (root->right != NULL) {
count += binarytree_count_recursive(root->right);
}
return count;
}

unsigned int binarytree_count(const binarytree *tree)
{
unsigned int count = 0;
if (tree->root != NULL) {
count = binarytree_count_recursive(tree->root);
}
return count;
}


## Counting leaf nodes

This is similar, except that we only return 1 if we are a leaf node. Otherwise, we recurse into the left and right subtrees and return the sum of the leaves in them.

unsigned int binarytree_count_leaves_recursive(const btnode *root)
{
unsigned int count = 0;
if (root->left == NULL && root->right == NULL) {
count = 1;
}
else {
if (root->left != NULL) {
count += binarytree_count_leaves_recursive(root->left);
}
if (root->right != NULL) {
count += binarytree_count_leaves_recursive(root->right);
}
}
return count;
}

unsigned int binarytree_count_leaves(const binarytree *tree)
{
unsigned int count = 0;
if (tree->root != NULL) {
count = binarytree_count_leaves_recursive(tree->root);
}
return count;
}


## Counting internal nodes

This is the counterpart of counting leaves. If we are an internal node, we count 1 for ourselves, then recurse into the left and right subtrees and sum the count of internal nodes in them.

unsigned int binarytree_count_internal_nodes_recursive(const btnode *root)
{
unsigned int count = 0;
if (root->left != NULL || root->right != NULL) {
count = 1;
if (root->left != NULL) {
count += binarytree_count_internal_nodes_recursive(root->left);
}
if (root->right != NULL) {
count += binarytree_count_internal_nodes_recursive(root->right);
}
}
return count;
}

unsigned int binarytree_count_internal_nodes(const binarytree *tree)
{
unsigned int count = 0;
if (tree->root != NULL) {
count = binarytree_count_internal_nodes_recursive(tree->root);
}
return count;
}


# Select server for windows

This is the Windows version of the Select Server.

#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif

#include <stdio.h>
#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG 10		/* Passed to listen() */

void handle(SOCKET newsock, fd_set *set)
{
/* send(), recv(), closesocket() */
/* Call FD_CLR(newsock, set) on disconnection */
}

int main(void)
{
WORD wVersion = MAKEWORD(2, 2);
WSADATA wsaData;
int iResult;
SOCKET sock;
fd_set socks;
fd_set readsocks;
SOCKET maxsock;
int reuseaddr = 1; /* True */
struct addrinfo hints, *res;

/* Initialise Winsock */
if (iResult = (WSAStartup(wVersion, &wsaData)) != 0) {
printf("WSAStartup failed: %d\n", iResult);
return 1;
}

/* Get the address info */
ZeroMemory(&hints, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
WSACleanup();
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
WSACleanup();
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, (const char*)&reuseaddr,
sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == SOCKET_ERROR) {
perror("bind");
WSACleanup();
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == SOCKET_ERROR) {
perror("listen");
WSACleanup();
return 1;
}

/* Set up the fd_set */
FD_ZERO(&socks);
FD_SET(sock, &socks);
maxsock = sock;

/* Main loop */
while (1) {
SOCKET s;
readsocks = socks;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == SOCKET_ERROR) {
perror("select");
WSACleanup();
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (FD_ISSET(s, &readsocks)) {
printf("Socket %d was ready\n", s);
if (s == sock) {
/* New connection */
SOCKET newsock;
struct sockaddr_in their_addr;
size_t size = sizeof(struct sockaddr_in);

newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
if (newsock == INVALID_SOCKET) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), htons(their_addr.sin_port));
FD_SET(newsock, &socks);
if (newsock > maxsock) {
maxsock = newsock;
}
}
}
else {
/* Handle read or disconnection */
handle(s, &socks);
}
}
}
}

/* Clean up */
closesocket(sock);
WSACleanup();

return 0;
}


# Select server

This server uses the select function to determine when sockets are ready for reading, and when clients have disconnected. It is not as fast as forking or using threads, and cannot exploit multi-cores, but is less resource intensive, and so will scale up to far more connections.

In order to prevent the handling of individual clients from starving others, it may necessary to limit how much data is read per client in response to each select call. Additionally, this example assumes that calls to recv will not block. If they can block, it may be necessary to put the socket in non-blocking mode using fcntl with the F_SETFL command and the O_NONBLOCK flag.

#include <stdio.h>
#include <string.h> /* memset() */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <netdb.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG     10  /* Passed to listen() */

void handle(int newsock, fd_set *set)
{
/* send(), recv(), close() */
/* Call FD_CLR(newsock, set) on disconnection */
}

int main(void)
{
int sock;
fd_set socks;
fd_set readsocks;
int maxsock;
int reuseaddr = 1; /* True */
struct addrinfo hints, *res;

/* Get the address info */
memset(&hints, 0, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &reuseaddr, sizeof(int)) == -1) {
perror("setsockopt");
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == -1) {
perror("bind");
return 1;
}

freeaddrinfo(res);

/* Listen */
if (listen(sock, BACKLOG) == -1) {
perror("listen");
return 1;
}

/* Set up the fd_set */
FD_ZERO(&socks);
FD_SET(sock, &socks);
maxsock = sock;

/* Main loop */
while (1) {
unsigned int s;
readsocks = socks;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == -1) {
perror("select");
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (FD_ISSET(s, &readsocks)) {
printf("socket %d was ready\n", s);
if (s == sock) {
/* New connection */
int newsock;
struct sockaddr_in their_addr;
socklen_t size = sizeof(struct sockaddr_in);
newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), htons(their_addr.sin_port));
FD_SET(newsock, &socks);
if (newsock > maxsock) {
maxsock = newsock;
}
}
}
else {
/* Handle read or disconnection */
handle(s, &socks);
}
}
}

}

close(sock);

return 0;
}


# Threaded server for Windows

This is the Windows version of the Threaded Server.

/*
*  Link with Ws2_32.lib
*/

#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif

#include <stdio.h>
#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>
#include <process.h> /* _beginthread() */

#define PORT    "32001" /* Port to listen on */
#define BACKLOG 10		/* Passed to listen() */

void handle(void *pParam)
{
/* send(), recv(), closesocket() */

free(pParam);
}

int main(void)
{
WORD wVersion = MAKEWORD(2, 2);
WSADATA wsaData;
int iResult;
SOCKET sock;
struct addrinfo hints, *res;
int reuseaddr = 1; /* True */

/* Initialise Winsock */
if ((iResult = WSAStartup(wVersion, &wsaData)) != 0) {
printf("WSAStartup failed: %d\n", iResult);
return 1;
}

/* Get the address info */
ZeroMemory(&hints, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == INVALID_SOCKET) {
perror("socket");
WSACleanup();
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, (const char *)&reuseaddr,
sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == SOCKET_ERROR) {
perror("bind");
WSACleanup();
return 1;
}

freeaddrinfo(res);

/* Listen */
if (listen(sock, BACKLOG) == SOCKET_ERROR) {
perror("listen");
WSACleanup();
return 1;
}

/* Main loop */
while(1) {
size_t size = sizeof(struct sockaddr);
struct sockaddr_in their_addr;
SOCKET newsock;

ZeroMemory(&their_addr, sizeof (struct sockaddr));
newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
if (newsock == INVALID_SOCKET) {
perror("accept\n");
}
else {
/* Use the new socket */
uintptr_t thread;
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), ntohs(their_addr.sin_port));
printf("New socket is %d\n", newsock);
/* Make a safe copy of newsock */
int *safesock = malloc(sizeof(int));
if (safesock) {
*safesock = newsock;
thread = _beginthread(handle, 0, safesock);
if (thread == -1) {
fprintf(stderr, "Couldn't create thread: %d\n", GetLastError());
closesocket(newsock);
}
}
else {
perror("malloc");
}
}
}

/* Clean up */
closesocket(sock);
WSACleanup();

return 0;
}


# Threaded server

This server creates a new thread for each client connection. This also permits as many connections as resources will allow. It is less resource intensive than forking.

It is the only option for multiprocessing on Windows, and on Linux is best suited to server computers with more than 2 cores.

When using multiple threads it is necessary to use synchronisation locks when accessing any shared application state, and also when calling many socket API functions.

/*
*  A threaded server
*  by Martin Broadhurst (www.martinbroadhurst.com)
*  Compile with -pthread
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* memset() */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <netdb.h>
#include <pthread.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG     10  /* Passed to listen() */

void *handle(void *pnewsock)
{
/* send(), recv(), close() */

free(pnewsock);

return NULL;
}

int main(void)
{
int sock;
pthread_t thread;
struct addrinfo hints, *res;
int reuseaddr = 1; /* True */

/* Get the address info */
memset(&hints, 0, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &reuseaddr, sizeof(int)) == -1) {
perror("setsockopt");
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == -1) {
perror("bind");
return 0;
}

freeaddrinfo(res);

/* Listen */
if (listen(sock, BACKLOG) == -1) {
perror("listen");
return 0;
}

/* Main loop */
while (1) {
socklen_t size = sizeof(struct sockaddr_in);
struct sockaddr_in their_addr;
int newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), htons(their_addr.sin_port));
/* Make a safe copy of newsock */
int *safesock = malloc(sizeof(int));
if (safesock) {
*safesock = newsock;
if (pthread_create(&thread, NULL, handle, safesock) != 0) {
fprintf(stderr, "Failed to create thread\n");
}
}
else {
perror("malloc");
}
}
}

close(sock);

return 0;
}


# Forked server

This server uses the fork function to create a new process for each client connection, permitting as many clients as resources will allow. It only works on Linux, and is best suited to server computers with 1 or 2 cores.

Notice that when using fork it is necessary to set up a signal handler for SIGCHLD in order to reap zombie processes.

#include <stdio.h>
#include <string.h> /* memset() */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <signal.h>
#include <sys/wait.h>
#include <netdb.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG     10  /* Passed to listen() */

/* Signal handler to reap zombie processes */
static void wait_for_child(int sig)
{
while (waitpid(-1, NULL, WNOHANG) > 0);
}

void handle(int newsock)
{
/* recv(), send(), close() */
}

int main(void)
{
int sock;
struct sigaction sa;
struct addrinfo hints, *res;
int reuseaddr = 1; /* True */

/* Get the address info */
memset(&hints, 0, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &reuseaddr, sizeof(int)) == -1) {
perror("setsockopt");
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == -1) {
perror("bind");
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == -1) {
perror("listen");
return 1;
}

freeaddrinfo(res);

/* Set up the signal handler */
sa.sa_handler = wait_for_child;
sigemptyset(&sa.sa_mask);
sa.sa_flags = SA_RESTART;
if (sigaction(SIGCHLD, &sa, NULL) == -1) {
perror("sigaction");
return 1;
}

/* Main loop */
while (1) {
struct sockaddr_in their_addr;
socklen_t size = sizeof(struct sockaddr_in);
int newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
int pid;

if (newsock == -1) {
perror("accept");
return 0;
}

printf("Got a connection from %s on port %d\n", inet_ntoa(their_addr.sin_addr),
htons(their_addr.sin_port));

pid = fork();
if (pid == 0) {
/* In child process */
close(sock);
handle(newsock);
return 0;
}
else {
/* Parent process */
if (pid == -1) {
perror("fork");
return 1;
}
else {
close(newsock);
}
}
}

close(sock);

return 0;
}


# Simple server for Windows

This is the Windows version of the Simple Server.

#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif

#include <stdio.h>
#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG 10		/* Passed to listen() */

void handle(SOCKET newsock)
{
/* send(), recv(), closesocket() */
}

int main(void)
{
WORD wVersion = MAKEWORD(2, 2);
WSADATA wsaData;
int iResult;
SOCKET sock;
struct addrinfo hints, *res;
int reuseaddr = 1; /* True */

/* Initialise Winsock */
if ((iResult = WSAStartup(wVersion, &wsaData)) != 0) {
printf("WSAStartup failed: %d\n", iResult);
return 1;
}

/* Get the address info */
ZeroMemory(&hints, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == INVALID_SOCKET) {
perror("socket");
WSACleanup();
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, (const char *)&reuseaddr, sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == SOCKET_ERROR) {
perror("bind");
WSACleanup();
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == SOCKET_ERROR) {
perror("listen");
WSACleanup();
return 1;
}

freeaddrinfo(res);

/* Main loop */
while(1) {
size_t size = sizeof(struct sockaddr);
struct sockaddr_in their_addr;
SOCKET newsock;

ZeroMemory(&their_addr, sizeof (struct sockaddr));
newsock = accept(sock, (struct sockaddr*)&their_addr, &size);
if (newsock == INVALID_SOCKET) {
perror("accept\n");
}
else {
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), ntohs(their_addr.sin_port));

handle(newsock);
}
}

/* Clean up */
closesocket(sock);
WSACleanup();

return 0;
}


# Simple Server

This server can only handle one client at a time, with up to 10 clients (the backlog argument to listen), being allowed to wait before connections are refused. This is suitable for a single-user desktop server or one in which connections are very short-lived.

#include <stdio.h>
#include <string.h> /* memset() */
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <netdb.h>

#define PORT    "32001" /* Port to listen on */
#define BACKLOG 10  /* Passed to listen() */

void handle(int newsock)
{
/* recv(), send(), close() */
}

int main(void)
{
int sock;
struct addrinfo hints, *res;
int reuseaddr = 1; /* True */

/* Get the address info */
memset(&hints, 0, sizeof hints);
hints.ai_family = AF_INET;
hints.ai_socktype = SOCK_STREAM;
if (getaddrinfo(NULL, PORT, &hints, &res) != 0) {
perror("getaddrinfo");
return 1;
}

/* Create the socket */
sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
if (sock == -1) {
perror("socket");
return 1;
}

/* Enable the socket to reuse the address */
if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &reuseaddr, sizeof(int)) == -1) {
perror("setsockopt");
return 1;
}

/* Bind to the address */
if (bind(sock, res->ai_addr, res->ai_addrlen) == -1) {
perror("bind");
return 1;
}

/* Listen */
if (listen(sock, BACKLOG) == -1) {
perror("listen");
return 1;
}

freeaddrinfo(res);

/* Main loop */
while (1) {
socklen_t size = sizeof(struct sockaddr_in);
struct sockaddr_in their_addr;
int newsock = accept(sock, (struct sockaddr*)&their_addr, &size);

if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
inet_ntoa(their_addr.sin_addr), htons(their_addr.sin_port));
handle(newsock);
}
}

close(sock);

return 0;
}