Find maximum element node in binary tree in Java - Recursive and Iterative

Topics covered

1. Find maximum element node in binary tree - Recursive
2. Find maximum element node in binary tree - Iterative
3. Complete sample program- recursive and iterative

In order to find maximum element in the binary tree we can use recursive post-order and iterative pre-order traversal. Instead of processing it we need check whether value of the given node is greater than current maxNode or not.

Sample code for searching  an element in binary tree in Java - recursive approach 

public Node findMaxInBinaryTreeRecursive(Node root, Node maxNode) {
 Node lMax = null, rMax = null;
 if (root != null) {
  Node lc = root.leftChild;
  Node rc = root.rightChild;
  if (lc != null) {
   lMax = findMaxInBinaryTreeRecursive(lc, maxNode);
  }
  if (rc != null) {
   rMax = findMaxInBinaryTreeRecursive(rc, maxNode);
  }

  if (lMax == null || rMax == null) {
   if (lMax == null && rMax == null) {
    maxNode = root;
   } else if (lMax == null && rMax != null) {
    maxNode = rMax.data > root.data ? rMax : root;
   } else if (lMax != null && rMax == null) {
    maxNode = lMax.data > maxNode.data ? lMax : maxNode;
   }
  } else {
   maxNode = lMax.data > rMax.data ? lMax : rMax;
   maxNode = root.data > maxNode.data ? root : maxNode;
  }

 }
 return maxNode;
}

Explanation:-Traverse binary tree  in post order manner(LDR) - first left subtree followed by right subtree and finally compare left, right and root node value and return maximum value out of them.Check if both left and right node and assign maxValue accordingly.

Sample code for searching  an element in binary tree in Java - iterative approach 

public Node findMaxInBinaryTreeIterative(Node root) {
 Node maxNode = root;
 Node temp;
 Stack<Node> stack = new Stack<>();
 stack.push(root);
 if (root != null) {
  while (!stack.isEmpty()) {
   temp = stack.pop();
   if (maxNode.data < temp.data) {
    maxNode = temp;
   }
   Node lc = temp.leftChild;
   Node rc = temp.rightChild;
   if (lc != null) {
    stack.push(lc);
   }
   if (rc != null) {
    stack.push(rc);
   }
  }
 }
 return maxNode;
}

Explanation:- Traverse binary tree in iterative pre-order manner and after popping an element from stack check for whether it's value is greater than current maximum value or not. If greater mark popped node as maximum

Complete sample program -finding maximum element in binary tree in Java (Iterative and Recursive) 

package com.devinline.trees;

import java.util.Stack;

public class FindMaxInBinaryTree {

public Node findMaxInBinaryTreeIterative(Node root) {
 Node maxNode = root;
 Node temp;
 Stack<Node> stack = new Stack<>();
 stack.push(root);
 if (root != null) {
  while (!stack.isEmpty()) {
   temp = stack.pop();
   if (maxNode.data < temp.data) {
    maxNode = temp;
   }
   Node lc = temp.leftChild;
   Node rc = temp.rightChild;
   if (lc != null) {
    stack.push(lc);
   }
   if (rc != null) {
    stack.push(rc);
   }
  }
 }
 return maxNode;
}

public Node findMaxInBinaryTreeRecursive(Node root, Node maxNode) {
 Node lMax = null, rMax = null;
 if (root != null) {
  Node lc = root.leftChild;
  Node rc = root.rightChild;
  if (lc != null) {
   lMax = findMaxInBinaryTreeRecursive(lc, maxNode);
  }
  if (rc != null) {
   rMax = findMaxInBinaryTreeRecursive(rc, maxNode);
  }

  if (lMax == null || rMax == null) {
   if (lMax == null && rMax == null) {
    maxNode = root;
   } else if (lMax == null && rMax != null) {
    maxNode = rMax.data > root.data ? rMax : root;
   } else if (lMax != null && rMax == null) {
    maxNode = lMax.data > maxNode.data ? lMax : maxNode;
   }
  } else {
   maxNode = lMax.data > rMax.data ? lMax : rMax;
   maxNode = root.data > maxNode.data ? root : maxNode;
  }

 }
 return maxNode;
}

 class Node {
  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

  public void setData(int data) {
   this.data = data;
  }

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(45));
   root.getRightChild().setLeftChild(new Node(123));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(563));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(234));
   root.getRightChild().getLeftChild().getRightChild()
     .setRightChild(new Node(48));
   return root;
  }
 }

 public static void main(String[] args) {
  FindMaxInBinaryTree itrObj = new FindMaxInBinaryTree();
  Node root = itrObj.new BinaryTree().createTree();
  Node node = itrObj.findMaxInBinaryTreeIterative(root);
  System.out.println("Iterative preorder traversal:-  " + node.data);
  Node max1 = itrObj.findMaxInBinaryTreeRecursive(root, itrObj.new Node(
    Integer.MIN_VALUE));
  System.out.println("Rec preorder traversal:-  " + max1.data);
 }

}

=======Sample output========
Iterative preorder traversal:-  563
Rec preorder traversal:-  563
=========================