Java Binary Tree Maximum Element
Chapter:
Data Structures
Last Updated:
11-11-2016 14:08:19 UTC
Program:
/* ............... START ............... */
import java.util.LinkedList;
import java.util.Queue;
public class JavaBinaryTreeMaximumElement {
public static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int data) {
this.data = data;
}
}
public static int getMaximumRec(TreeNode root) {
int max = Integer.MIN_VALUE;
int value = 0;
int left, right;
if (root != null) {
value = root.data;
left = getMaximumRec(root.left);
right = getMaximumRec(root.right);
if (left > right) {
max = left;
} else {
max = right;
}
if (max < value) {
max = value;
}
}
return max;
}
public static int getMaximumItr(TreeNode startNode) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(startNode);
int max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
TreeNode tempNode = queue.poll();
if (max < tempNode.data)
max = tempNode.data;
if (tempNode.left != null)
queue.add(tempNode.left);
if (tempNode.right != null)
queue.add(tempNode.right);
}
return max;
}
public static void main(String[] args) {
JavaBinaryTreeMaximumElement bi = new JavaBinaryTreeMaximumElement();
// Creating a binary tree
TreeNode rootNode = createBinaryTree();
System.out.println("Max node using recursion :" + getMaximumRec(rootNode));
System.out.println("Max node using iteration :" + getMaximumItr(rootNode));
}
public static TreeNode createBinaryTree() {
TreeNode rootNode = new TreeNode(40);
TreeNode node20 = new TreeNode(20);
TreeNode node10 = new TreeNode(10);
TreeNode node30 = new TreeNode(30);
TreeNode node60 = new TreeNode(60);
TreeNode node50 = new TreeNode(50);
TreeNode node70 = new TreeNode(70);
rootNode.left = node20;
rootNode.right = node60;
node20.left = node10;
node20.right = node30;
node60.left = node50;
node60.right = node70;
return rootNode;
}
}
/* ............... END ............... */
Output
Max node using recursion :70
Max node using iteration :70
Notes:
-
Recursive solution
- Find maximum element in left subtree.
- Find maximum element in right subtree.
- Compare maximum of above subtrees to current node.
- We will find maximum element with above steps.
- Iterative solution
- Iterative solution will be similar to level order traversal. When we are popping element from queue, we will check max.
Tags
Binary Tree Maximum Element, Java, Data Structures