Home Trees Find the maximum element in a binary tree without recursion.

Find the maximum element in a binary tree without recursion.

by nikoo28
0 comment

Question: Given the root pointer to a binary tree, find the maximum element present in it.

Input: Sample Tree (Pointer to node 1 is given)
sample_treeOutput: Maximum = 9

We discussed how to find the maximum element in a binary tree using recursion in this post.

That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that it passes through each element of the binary tree. Utilizing this property we can keep a track of the maximum element encountered in complete traversal. Then simply return the element. Here is an implementation to find the maximum element without using recursion.

#include<stdio.h>
#define MIN -65535
int findMaxInTreeNonRecursive(struct binaryTreeNode * root)
{
	// Initialize max with a very less value;
	int max = MIN;

	// Level Order Traversal
	struct binaryTreeNode * temp = NULL;
	struct queue * Q = NULL;
	if(root == NULL)
		return;

	Q = enQueue(Q, root);

	while(!isQueueEmpty(Q))
	{
		temp = Q -> front -> data;

		Q = deQueue(Q);

		// Find the max value
		if(temp -> data > max)
			max = temp -> data;

		if(temp -> left)
			Q = enQueue(Q, temp -> left);
		if(temp -> right)
			Q = enQueue(Q, temp -> right);
	}
	free(Q);

	return max;
}

Time Complexity:- O(n)
Space Complexity:- O(n)

You can download the complete working code here. Use your favorite editor to open it.

Ideone link:- http://ideone.com/7GvTS5

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More