Find minimum & maximum element in binary tree (recursive /java/ example)

• Given a binary tree, find out minimum & maximum value using recursive algorithm.
• Traverse binary tree using depth first search (dfs) algorithm.
• We have already discussed, to find largest element in a binary tree using bfs algorithm.
• The algorithm of current problem is quite similar to:
  • Find height of binary tree using recursion.

Let us look into couple of examples to find out largest & smallest element in a binary tree using java

Example 1: find maximum element in binary tree (recursive)

Fig 2: Max element in Tree

• Go to Node B (50)
• Find the maximum element in left subtree
  • Maximum value is 25.
• Find the maximum element in right subtree
  • Maximum value is 80.
• Maximum value at Node B is.
  • Max(Value in left subtree, max value in right subtree, Node B value).
  • Max ( 25, 80, 50) = 80

So, maximum value of Fig 2 is 80

Example 2: find maximum element in binary tree (DFS) using java

Fig 3: Maximum node value binary tree

• Go to Node A (60)
• Find maximum value in left subtree (Node B).
  • Apply Example 1 algorithm at Node B.
  • Max value at Node B is 80.
• Find maximum value in right subtree (Node C).
  • Apply Example 1 algorithm at Node C.
  • Max value at Node B is 90.
• Maximum value at Node A is.
  • Max of (value in left subtree, value in right sub tree, value at Node A).
    • Max ( 80, 90, 60) = 90.
• Maximum value of binary tree is 90

We can calculate maximum value of binary tree using above algorithm. Similarly, we can find the minimum value in binary tree. Instead of finding the maximum value at any node, we will find the minimum value.
The time complexity of algorithm is O(n).

Program – find largest & smallest element in binary tree using java

1.) MaxMinElementInBTree Class:

• MaxMinElementInBTree class is responsible for finding minimum & maximum element in a binary tree.
  • maxElementInBTree method: find maximum value in a binary tree.
  • minElementInBTree method: find minimum value in a binary tree.

package org.learn.Question;

public class MaxMinElementInBTree {

	public static int maxElementInBTree(Node root) {
		if (null == root)
			return Integer.MIN_VALUE;

		int currentNodeValue = root.data;
		int hLeftSub = maxElementInBTree(root.left);
		int hRightSub = maxElementInBTree(root.right);
		return Math.max(Math.max(hLeftSub, hRightSub), currentNodeValue);
	}

	public static int minElementInBTree(Node root) {
		if (null == root)
			return Integer.MAX_VALUE;

		int data = root.data;
		int left = minElementInBTree(root.left);
		int right = minElementInBTree(root.right);
		return Math.min(data, Math.min(left, right));
	}
}

2.) Node:

• Node class representing the nodes in a binary tree.

package org.learn.Question;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}

	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

• We are creating binary tree in main method.
• We are calling method of MaxMinElementInBTree class, to find max & min element in a binary tree.

package org.learn.Client;

import org.learn.Question.MaxMinElementInBTree;
import org.learn.Question.Node;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(60);
		// Level 1
		Node B = Node.createNode(50);
		Node C = Node.createNode(90);
		// Level 2
		Node D = Node.createNode(25);
		Node E = Node.createNode(80);
		Node F = Node.createNode(75);
		Node G = Node.createNode(45);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;

		int maxElement = MaxMinElementInBTree.maxElementInBTree(A);
		System.out.println("Maximum element in a binary tree: " + maxElement);

		int minElement = MaxMinElementInBTree.minElementInBTree(A);
		System.out.println("Minimum element in a binary tree: " + minElement);
	}
}

Output – minimum & maximum element in binary tree using java

Maximum element in a binary tree: 90
Minimum element in a binary tree: 25