binary tree problems with solution

binary tree problems with solution

today is saturday and was catching upon some blogs. Then come across some binary tree algorithms and it reminded me the famous stanford binary tree questions.. decided to work on those and got to the mid of it..
Actually the questions get harder as you go further.. the first 7 are relatively easy..
I will continue to work on them and post my solution here.
the solutions are given on the this page but, it is advisable to work them out without looking a the solution..

here it is!


#include
#include
/*
 * @author http://gullele.com
 * binary tree problems and solutions.
 */
struct Node
{
	int number;
	struct Node *left;
	struct Node *right;
};

int minValue(struct Node *head);
int maxDepth(struct Node *head);
int countNode(struct Node *head);
void printTree(struct Node *head);
void postOrderTraversal(struct Node *head);
struct Node *createNode(int value);
int hasPathSum(struct Node *head, int sum);
struct Node *head = NULL;
struct Node *head2=NULL;
int main()
{
	struct Node *head=createNode(10);
	struct Node *left=createNode(8);
	struct Node *right=createNode(15);
	struct Node *right1=createNode(5);
	struct Node *right2=createNode(1);
	head->left=left;
	head->right=right;
	left->left=right1;
	right1->left=right2;

	struct Node *head2=createNode(5);
	struct Node *two=createNode(2);
	struct Node *seven=createNode(7);
	struct Node *eleven=createNode(11);
	struct Node *lfour=createNode(4);
	struct Node *thirteen=createNode(13);
	struct Node *eight=createNode(8);
	struct Node *rfour=createNode(4);
	struct Node *one=createNode(1);
	
	head2->left=lfour;
	head2->right=eight;
	lfour->left=eleven;
	eleven->left=seven;
	eleven->right=two;
	eight->left=thirteen;
	eight->right=rfour;
	rfour->right=one;

	printf("Size of the tree is %d n", countNode(head));
	printf("Max depth is %d n", maxDepth(head)-1);
	printf("Minimum Value is %d n", minValue(head));
	printTree(head2);
	printf("n");
	postOrderTraversal(head);
	int hasSum = hasPathSum(head2,17);
	if(hasSum)
		printf("it has sum");
	else
		printf("it does not has sum");
	return 0;
}

/**
 * Takes the head of the binary tree and counts how many children are there in the tree
 * it will recursively count the left and right nodes to come to the conclusion
 */
int countNode(struct Node *head)
{
	if (head==NULL)
	{
		return 0;
	}
	return countNode(head->left)+1+countNode(head->right);
}

/**
 * Finds the maximum depth of the tree
 *
 */
int maxDepth(struct Node *head)
{
	int maxLength = 0;
	if (head==NULL)
	{
		return 0;
	}
	else
	{
		int leftMax = 1 + maxDepth(head->left);
		int rightMax = 1 + maxDepth(head->right);
		if (leftMax > rightMax)
		{
			return leftMax;
		}
		return rightMax;
	}
}

/**
 * Works on the Binary Search Tree - since on the BST, for sure the left child is always lesser in value.
 */
int minValue(struct Node *head)
{
	if(head==NULL)
		return 0; //might not be valid answer here
	struct Node *current=head;
	while(current->left!=NULL)
	{
		current=current->left;
	}
	return current->number;
}

/**
 * Prints the value of the BST
 * this is inorder traversal
 */
void printTree(struct Node *head)
{
	if (head==NULL)
	{
		return;
	}
	else
	{
		printTree(head->left);
		printf("%d, ", head->number);
		printTree(head->right);
	}
}	

int hasPathSum(struct Node *head, int sum)
{
	int localsum = 0;
	if (head == NULL)
	{
		return 0;
	}
	else if(head->left==NULL && head->right==NULL)
	{
		return (sum-head->number == 0);
	}
	else
	{
		int temp=sum-head->number;
		return hasPathSum(head->left, temp) || hasPathSum(head->right, temp);
	}
}
/**
 * Post order traversal version of the tree traversal
 */
void postOrderTraversal(struct Node *head)
{
	if (head==NULL)
	{
		return;
	}
	else
	{
		printTree(head->left);
		printTree(head->right);
		printf("%d, ", head->number);
	}
}

/**
 * Create new node
 */
struct Node *createNode(int value)
{
	struct Node *newNode=malloc(sizeof(struct Node));
	newNode->number=value;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}


J2EE Maven Eclipse Hello World Tutorial Part Two

Java solution for checking anagram strings – tell if phrases are anagrams

Check if two strings are anagrams or not

Find K Complementary numbers from array Java implementation

how to get user input and process it in nodejs tutorial

how to display html files from node js example tutorial

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*