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);
int iResult;
SOCKET sock;
fd_set socks;
SOCKET maxsock;
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) {
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 */
sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
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;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == SOCKET_ERROR) {
perror("select");
WSACleanup();
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (s == sock) {
/* New connection */
SOCKET newsock;

if (newsock == INVALID_SOCKET) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
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;
int maxsock;
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) {
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 */
perror("setsockopt");
return 1;
}

/* Bind to the address */
perror("bind");
return 1;
}

/* 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;
if (select(maxsock + 1, &readsocks, NULL, NULL, NULL) == -1) {
perror("select");
return 1;
}
for (s = 0; s <= maxsock; s++) {
if (s == sock) {
/* New connection */
int newsock;
if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
FD_SET(newsock, &socks);
if (newsock > maxsock) {
maxsock = newsock;
}
}
}
else {
/* Handle read or disconnection */
handle(s, &socks);
}
}
}

}

close(sock);

return 0;
}


This is the Windows version of the Threaded 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(void *pParam)
{
/* send(), recv(), closesocket() */

free(pParam);
}

int main(void)
{
WORD wVersion = MAKEWORD(2, 2);
int iResult;
SOCKET sock;
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) {
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 */
sizeof(int)) == SOCKET_ERROR) {
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
perror("bind");
WSACleanup();
return 1;
}

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

/* Main loop */
while(1) {
SOCKET newsock;

if (newsock == INVALID_SOCKET) {
perror("accept\n");
}
else {
/* Use the new socket */
printf("Got a connection from %s on port %d\n",
printf("New socket is %d\n", newsock);
/* Make a safe copy of newsock */
int *safesock = malloc(sizeof(int));
if (safesock) {
*safesock = newsock;
fprintf(stderr, "Couldn't create thread: %d\n", GetLastError());
closesocket(newsock);
}
}
else {
perror("malloc");
}
}
}

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

return 0;
}


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.

/*
*/

#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>

#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;
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) {
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 */
perror("setsockopt");
return 1;
}

/* Bind to the address */
perror("bind");
return 0;
}

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

/* Main loop */
while (1) {
if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",
/* Make a safe copy of newsock */
int *safesock = malloc(sizeof(int));
if (safesock) {
*safesock = newsock;
}
}
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;
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) {
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 */
perror("setsockopt");
return 1;
}

/* Bind to the address */
perror("bind");
return 1;
}

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

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

/* Main loop */
while (1) {
int pid;

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

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);
int iResult;
SOCKET sock;
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) {
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 */
perror("setsockopt");
WSACleanup();
return 1;
}

/* Bind to the address */
perror("bind");
WSACleanup();
return 1;
}

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

/* Main loop */
while(1) {
SOCKET newsock;

if (newsock == INVALID_SOCKET) {
perror("accept\n");
}
else {
printf("Got a connection from %s on port %d\n",

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;
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) {
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 */
perror("setsockopt");
return 1;
}

/* Bind to the address */
perror("bind");
return 1;
}

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

/* Main loop */
while (1) {

if (newsock == -1) {
perror("accept");
}
else {
printf("Got a connection from %s on port %d\n",