Find maximum element in binary tree without recursion.

We could have used either PreOrder, InOrder or PostOrder traversal to find the maximum in a Tree but as it is mentioned that we need to find the maximum without using Recursion.

Using Level Order Traversal we can find the Maximum element. We just need to observe the elements data while deleting.

Java Implementation is as below:

package askgif.tree;

import java.util.LinkedList;
import java.util.Queue;

class Node
{
 int data;
 Node left, right;
 
 public Node(int item)
 {
 data = item;
 left = right = null;
 }
}

class BinaryTree
{
 Node root;
 
 BinaryTree()
 {
 root = null;
 }
 
}

public class TreeQuestions {

	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		Node root = new Node(1);
		binaryTree.root = root;
		binaryTree.root.left = new Node(2);
		binaryTree.root.right = new Node(3);
		
		binaryTree.root.left.left = new Node(4);
		binaryTree.root.left.right = new Node(5);
 
 System.out.println(FindMaxElement(root));

	}

	private static int FindMaxElement(Node treeNode) {
		if(treeNode == null)
			return -1;
		
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(treeNode);
		int max = -1;
		while(!queue.isEmpty()) {
			Node temp = queue.remove();
			if(temp.data > max)
				max = temp.data;
			if(temp.left != null)
				queue.add(temp.left);
			if(temp.right != null)
				queue.add(temp.right);
		}
		
		return max;
	}

}

output:

5

Time Complexity: O(n) as we are traversing through each node once.

Space Complexity: O(n) for Queue.