Kth smallest element in a perfect binary search tree

// C program for
// Kth smallest element in a perfect binary search tree
#include <stdio.h>
#include <stdlib.h>

 // Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};

// Binary search tree
struct BST
{
	struct TreeNode *root;
};
// Create new tree
struct BST *newTree()
{
	// Create a dynamic tree 
	struct BST *tree = (struct BST *) malloc(sizeof(struct BST));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	// return new tree
	return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = 
      (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Adding a new node in binary search tree
void addNode(struct BST *tree, int data)
{
	struct TreeNode *node = getNode(data);
	if (node != NULL)
	{
		if (tree->root == NULL)
		{
			tree->root = node;
		}
		else
		{
			struct TreeNode *auxiliary = tree->root;
			// Add new node in binary search tree
			while (auxiliary != NULL)
			{
				if (data > auxiliary->data)
				{
					if (auxiliary->right == NULL)
					{
						// Add new node at right child
						auxiliary->right = node;
						return;
					}
					auxiliary = auxiliary->right;
				}
				else
				{
					if (auxiliary->left == NULL)
					{
						// Add new node at left child
						auxiliary->left = node;
						return;
					}
					auxiliary = auxiliary->left;
				}
			}
		}
	}
}
// Count number of nodes in binary tree
int countNode(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return countNode(node->left) + countNode(node->right) + 1;
}
struct TreeNode *findKthSmallestNode(struct TreeNode *node, int k, int n)
{
	if (node == NULL)
	{
		return NULL;
	}
	int mid = (n / 2) + 1;
	if (mid == k)
	{
		// Get resultant node
		return node;
	}
	if (k < mid)
	{
		return findKthSmallestNode(node->left, k, mid - 1);
	}
	else
	{
		return findKthSmallestNode(node->right, k - mid, mid - 1);
	}
}
void printInorder(struct TreeNode *node)
{
	if (node != NULL)
	{
		printInorder(node->left);
		printf("  %d", node->data);
		printInorder(node->right);
	}
}
void kthSmallestNode(struct TreeNode *node, int k)
{
	if (node == NULL)
	{
		// When empty tree
		return;
	}
	// Count number of nodes in binary tree
	int n = countNode(node);
	if (k <= 0 || n < k)
	{
		// Invalid k
		return;
	}
	// Find kth smallest
	struct TreeNode *result = findKthSmallestNode(node, k, n);
	// Display calculated result
	printf("\n (%d)-th smallest is : %d", k, result->data);
}
int main(int argc, char
	const *argv[])
{
	struct BST *tree = newTree();
	/*
	              10 
	             /  \
	            /    \
	           /      \ 
	          /        \
	         /          \                           
	        /            \    
	       4               25    
	      /  \            /  \   
	     /    \          /    \      
	    2       7       19     29
	   / \     / \     / \     / \ 
	  /   \   /   \   /   \   /   \
	 -1    3 6     8 12   21 27   34 
	
	-----------------
	  Constructing binary search tree
	*/
	addNode(tree, 10);
	addNode(tree, 4);
	addNode(tree, 2);
	addNode(tree, -1);
	addNode(tree, 3);
	addNode(tree, 7);
	addNode(tree, 6);
	addNode(tree, 8);
	addNode(tree, 25);
	addNode(tree, 19);
	addNode(tree, 12);
	addNode(tree, 21);
	addNode(tree, 29);
	addNode(tree, 27);
	addNode(tree, 34);
	// Print tree element
	printInorder(tree->root);
	// Test Cases
	kthSmallestNode(tree->root, 4);
	kthSmallestNode(tree->root, 8);
	kthSmallestNode(tree->root, 5);
	kthSmallestNode(tree->root, 1);
	kthSmallestNode(tree->root, 14);
	return 0;
}

input

  -1  2  3  4  6  7  8  10  12  19  21  25  27  29  34
 (4)-th smallest is : 4
 (8)-th smallest is : 10
 (5)-th smallest is : 6
 (1)-th smallest is : -1
 (14)-th smallest is : 29