Binary Tree in Java

Binary tree in java
A binary tree is a tree data structure in which each node has at most two
children, which are referred to as the left child and the right child
Example of binary tree:
I have posted various programs on binary tree so that you can practice them
for interviews and it will also help in understanding recursion.
Binary tree traversals:
PreOrder traversal - In PreOrder traversal,each node is processed before either
of its sub-trees.In simpler words,Visit each node before its children.
InOrder traversal : In InOrder traversal,each node is processed between
subtrees.In simpler words,Visit left subtree, node and then right subtree.
PostOrder traversal: In PostOrder traversal,each node is processed after
subtrees traversal.In simpler words,Visit left subtree, right subtree and then
node.
Level order traversal : In Level order traversal, tree is traversed by each level.
It is same as breadth first search.
Spiral/Zigzag order traversal : In spiral order traversal, tree is traversed in
spiral shape.
Binary tree reverse level order traversal: It is similar to level order but in
reverse
Binary tree boundary traversal : This traversal traverse boundary of binary tree
Binary Tree PreOrder traversal in java

PreOrder traversal:
In PreOrder traversal,each node is processed before either of its sub-trees.In
simpler words,Visit each node before its children.
Steps for PreOrder traversal are:
Visit the node.
Traverse the left subtree in PreOrder.
Traverse the right subtree in PreOrder.
There can be two ways of implementing it
Recursive
Iterative
Recursive solution:
Recursive solution is very straight forward.Below diagram will make you
understand recursion better.
Code for recursion will be:

view plainprint?
1. public void preorder(TreeNode root) {
2.
3.
if(root != null) {
//Visit the node by Printing the node data
4.
System.out.printf("%d ",root.data);
5.
preorder(root.left);
6.
preorder(root.right);
7.
8.
}
}
Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to
iterative, we will use explicit stack.

Steps for iterative solution:
1. Create empty stack and pust root node to it.
2. Do the following when stack is not empty
o
Pop a node from stack and print it
Push right child of popped node to stack
Push left child of popped node to stack
We are pushing right child first, so it will be processed after left subtree as
Stack is LIFO.
view plainprint?
1.
2. public void preorderIter(TreeNode root) {
3.
4.
5.
if(root == null)
return;
6.
7.
Stack<TreeNode> stack = new Stack<TreeNode>();
8.
stack.push(root);
9.
10.
while(!stack.empty()){
11.
12.
TreeNode n = stack.pop();
13.
System.out.printf("%d ",n.data);
14.
15.
16.
if(n.right != null){
17.
stack.push(n.right);
18.
19.
if(n.left != null){
20.
stack.push(n.left);
21.
22.
23.
24.
25.
Example:
Lets say your binary tree is :
Lets create java program for PreOrder traversal:

view plainprint?
1.
2. package org.arpit.java2blog;
3.
4. import java.util.Stack;
5.
6. public class BinaryTree {

7.
8.
9.
public static class TreeNode
10. {
11. int data;
12. TreeNode left;
13. TreeNode right;
14. TreeNode(int data)
15. {
16.
this.data=data;
17. }
18. }
19.
20.
// Recursive Solution
21. public void preorder(TreeNode root) {

22.
if(root != null) {
23.
//Visit the node-Printing the node data
24.
25.
preorder(root.left);
26.
preorder(root.right);
27.
28. }
29.
30. // Iterative solution

31. public void preorderIter(TreeNode root) {
32.
33.
if(root == null)
34.
return;
35.
36.
Stack<TreeNode> stack = new Stack<TreeNode>();
37.
stack.push(root);
38.
39.
while(!stack.empty()){
40.
41.
TreeNode n = stack.pop();
42.
43.
44.
45.
if(n.right != null){
46.
stack.push(n.right);
47.
48.
if(n.left != null){
49.
stack.push(n.left);
50.
51.
52.
53.
54.
55.
56. public static void main(String[] args)
57. {
58. BinaryTree bi=new BinaryTree();
59. // Creating a binary tree
60. TreeNode rootNode=createBinaryTree();
61. System.out.println("Using Recursive solution:");
62.
63. bi.preorder(rootNode);
64.
65. System.out.println();
66. System.out.println("-------------------------");
67. System.out.println("Using Iterative solution:");
68.
69. bi.preorderIter(rootNode);
70. }
71.
72. public static TreeNode createBinaryTree()
73. {
74.
75. TreeNode rootNode =new TreeNode(40);
76. TreeNode node20=new TreeNode(20);

82.
83. rootNode.left=node20;
84. rootNode.right=node60;
85.
86. node20.left=node10;
87. node20.right=node30;
88.
91.
92. return rootNode;
93. }
94.}
Run above program and you will get following output:
view plainprint?
1.
2. Using Recursive solution:
3. 40 20 10 30 60 50 70
4. ------------------------5. Using Iterative solution:
6. 40 20 10 30 60 50 70
Binary Tree PostOrder traversal in java

PostOrder traversal:
In PostOrder traversal,each node is processed after subtrees traversal.In
simpler words,Visit left subtree, right subtree and then node.
Steps for PostOrder traversal are:
Traverse the left subtree in PostOrder.
Traverse the right subtree in PostOrder.
Visit the node.
Recursive
Iterative
Recursive solution:

public void postOrder(TreeNode root) {
if(root != null) {
postOrder(root.left);
postOrder(root.right);
}
}
Iterative solution:
1. Create an empty stack s and set currentNode =root.

2. while currentNode is not NULL Do following
1. Push currentNode 's right child and then currentNode to stack.
2. Set currentNode =currentNode .left
3. Pop an node from stack and set it as root and set it to currentNode
1. If the popped node has a right child and the right child is at top of
stack, then remove the right child from stack, push the current
node back and set currentNode as currentNode 's right child.
2. Else print currentNode 's data and set currentNode as NULL.
4. Repeat steps 2 and 3 while stack is not empty.
public void postorderIter( TreeNode root) {
if( root == null ) return;
Stack<TreeNode> s = new Stack<TreeNode>( );
TreeNode current = root;
while( true ) {
if( current != null ) {
if( current.right != null )
s.push( current.right );
s.push( current );
current = current.left;
continue;
}
if( s.isEmpty( ) )
return;
current = s.pop( );
if( current.right != null && ! s.isEmpty( ) && current.right ==

s.peek( ) ) {
s.pop( );
s.push( current );
current = current.right;
} else {
System.out.print( current.data + " " );
current = null;
}
}
}
Lets create java program for InOrder traversal:
package org.arpit.java2blog;
import java.util.Stack;
public class BinaryTree {
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
public void postOrder(TreeNode root) {
if(root != null) {
postOrder(root.left);
postOrder(root.right);
}
}
// Iterative solution
public void postorderIter( TreeNode root) {
if( root == null ) return;
Stack<TreeNode> s = new Stack<TreeNode>( );
TreeNode current = root;
while( true ) {
if( current != null ) {
if( current.right != null )
s.push( current.right );
s.push( current );
current = current.left;
continue;
}
if( s.isEmpty( ) )
return;
current = s.pop( );
if( current.right != null && ! s.isEmpty( ) && current.right ==
s.peek( ) ) {
s.pop( );
s.push( current );
current = current.right;
} else {
System.out.print( current.data + " " );
current = null;
}
}
}
public static void main(String[] args)
{
BinaryTree bi=new BinaryTree();
// Creating a binary tree
TreeNode rootNode=createBinaryTree();
System.out.println("Using Recursive solution:");
bi.inOrder(rootNode);
System.out.println();
System.out.println("-------------------------");
System.out.println("Using Iterative solution:");
bi.inOrderIter(rootNode);
}
public static TreeNode createBinaryTree()
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
rootNode =new TreeNode(40);

node20=new TreeNode(20);
rootNode.left=node20;
rootNode.right=node60;
node20.left=node10;
node20.right=node30;
node60.left=node50;
return rootNode;
Using Recursive solution:

10 30 20 50 70 60 40
------------------------Using Iterative solution:
10 30 20 50 70 60 40
Binary Tree InOrder traversal in java

InOrder traversal:
In InOrder traversal,each node is processed between subtrees.In simpler
words,Visit left subtree, node and then right subtree.
Steps for InOrder traversal are:
Traverse the left subtree in InOrder.
Visit the node.
Traverse the right subtree in InOrder.
Recursive
Iterative
Recursive solution:

view plainprint?
1. public void inOrder(TreeNode root) {
2.
if(root != null) {
3.
inOrder(root.left);
4.
5.
6.
inOrder(root.right);
7.
8.
}
}
Iterative solution:
For recursion, we use implicit stack. So here to convert recursive solution to
iterative, we will use explicit stack.
1. Create an empty stack s and Initialize current node as root
2. Push the current node to s and set currentNode = currentNode.left until

currentNode is NULL
3. If currentNode is NULL and s is not empty then
o
o
o
Pop the top node from stack and print it

set currentNode = currentNode.right
go to step 2
4. If stack is empty and currentNode is also null then we are done with it
view plainprint?
1.
2. public void inOrderIter(TreeNode root) {
3.
4.
5.
if(root == null)
return;
6.
7.
Stack<TreeNode> s = new Stack<TreeNode>();
8.
TreeNode currentNode=root;
9.
10. while(!s.empty() || currentNode!=null){
11.
12.
if(currentNode!=null)
13.
14.
s.push(currentNode);
15.
currentNode=currentNode.left;
16.
17.
else
18.
19.
TreeNode n=s.pop();
20.
21.
currentNode=n.right;
22.
23. }
24. }
Lets create java program for InOrder traversal:

view plainprint?
1.
3.
4. import java.util.Stack;
5.
7.
8.
9.
10. {
11. int data;
12. TreeNode left;
13. TreeNode right;
15. {
16.
this.data=data;
17. }
18. }
19.
20.
21. public void inOrder(TreeNode root) {

22. if(root != null) {
23.
inOrder(root.left);
24.
25.
26.
inOrder(root.right);
27. }
28. }
29.
30. // Iterative solution
31. public void inOrderIter(TreeNode root) {
32.
33. if(root == null)
34.
return;
35.
36. Stack<TreeNode> s = new Stack<TreeNode>();
37. TreeNode currentNode=root;
38.
39. while(!s.empty() || currentNode!=null){
40.
41.
if(currentNode!=null)
42.
43.
s.push(currentNode);
44.
currentNode=currentNode.left;
45.
46.
else
47.
48.
TreeNode n=s.pop();
49.
50.
currentNode=n.right;
51.
52. }
53. }
54.
56. {
60. System.out.println("Using Recursive solution:");
61.
62. bi.inOrder(rootNode);
63.
64. System.out.println();
65. System.out.println("-------------------------");
66. System.out.println("Using Iterative solution:");
67.
68. bi.inOrderIter(rootNode);
69. }
70.
72. {
73.
81.
84.
87.
90.
92. }
93.}
view plainprint?
1.
2. Using Recursive solution:
3. 10 20 30 40 50 60 70
4. ------------------------5. Using Iterative solution:
6. 10 20 30 40 50 60 70
Binary Tree Level Order traversal in java

Level Order traversal:
Level order traversal of below tree will be:
We will use Queue for Level Order traversal.This algorithm is very similar to
Breadth first search of graph.
Steps for Level order traversal algorithm:
1. Create empty queue and pust root node to it.
2. Do the following when queue is not empty
o
Pop a node from queue and print it
Push left child of popped node to queue if not null
Push right child of popped node to queue if not null
// prints in level order

public static void levelOrderTraversal(TreeNode startNode) {
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(startNode);
while(!queue.isEmpty())
{
TreeNode tempNode=queue.poll();
System.out.printf("%d ",tempNode.data);
if(tempNode.left!=null)
queue.add(tempNode.left);
if(tempNode.right!=null)
queue.add(tempNode.right);
}
}
Example:
So Level Order traversal will work as below:
Lets create java program for level order traversal:
import java.util.Queue;
import java.util.LinkedList;
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// prints in level order
public static void levelOrderTraversal(TreeNode startNode) {
{
}
}
{
System.out.println("Level Order traversal of binary tree will be:");
levelOrderTraversal(rootNode);
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
return rootNode;
}
}
Level Order traversal of binary tree will be:

40 20 60 10 30 50 70
Spiral/Zigzag level order traversal of binary tree in java

Spiral/Zigzag Level Order traversal:
Spiral/Zigzag Level order traversal of below tree will be:
Steps for solution:

1. Create an empty stack s and push root to it.
2. while stack is not NULL Do following
1. Create a empty stack called tempStack.
2. Pop a node from stack and push it to tempStack depending on
directionFlag
3. Change directionFlag to change the direction of traversal
4. set stack=tempStack
// prints in Spiral/Zigzag level order

public static void spiralOrZigzagLevelOrder(TreeNode root) {
if(root==null) return;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
boolean directionflag=false;
while(!stack.isEmpty())
{
Stack<TreeNode> tempStack=new Stack<TreeNode>();
{
TreeNode tempNode=stack.pop();
if(!directionflag)
{
tempStack.push(tempNode.left);
tempStack.push(tempNode.right);
}else
{
}
}
// for changing direction
directionflag=!directionflag;
}
stack=tempStack;
Example:
So Spiral/Zigzag Level Order traversal will work as below:

Lets create java program for Spiral/Zigzag Level traversal:
import java.util.Queue;
import java.util.LinkedList;
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// prints spiral/zigzag level order
public static void spiralOrZigzagLevelOrder(TreeNode root) {
if(root==null) return;
stack.push(root);
boolean directionflag=false;
{
Stack<TreeNode> tempStack=new Stack<TreeNode>();

{
TreeNode tempNode=stack.pop();
if(!directionflag)
{
}else
{
}
}
// for changing direction
directionflag=!directionflag;
}
stack=tempStack;
}
{
System.out.println("Spiral/Zigzag traversal of binary tree :");
spiralOrZigzagLevelOrder(rootNode);
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
node10.left=node5;
return rootNode;
}
}
Spiral/Zigzag traversal of binary tree :

40 60 20 10 30 50 70 55 5
Reverse level order traversal of binary tree in java

Reverse Level Order traversal:
Reverse Level order traversal of below tree will be:
We will use stack for Reverse Level Order traversal.

Steps for Reverse Level order traversal algorithm:
1. Create empty queue and push root node to it.

2. Do the following when queue is not empty
o
Pop a node from queue and print it
Push right child of popped node to queue if not null
Push left child of popped node to queue if not null
Push current node to stack
Pop node from stack and print it
// prints in reverse level order

public static void reverseLevelOrderTraversal(TreeNode startNode) {
{
stack.push(tempNode);
}
while(!stack.empty())
System.out.print(stack.pop().data+" " );
}
Example:
So Reverse Level Order traversal will work as below:

Lets create java program :
import
import
import
public
java.util.LinkedList;
java.util.Queue;
java.util.Stack;
class BinaryTree {

{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// prints in reverse level order
public static void reverseLevelOrderTraversal(TreeNode startNode) {
{
stack.push(tempNode);
}
while(!stack.empty())
System.out.print(stack.pop().data+" " );
}
{
System.out.println("Reverse Level Order traversal of binary tree will
be:");
reverseLevelOrderTraversal(rootNode);
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
return rootNode;
}
Reverse Level Order traversal of binary tree will be:

10 30 50 70 20 60 40
Boundary traversal of binary tree in java
Lets understand boundary traversal of binary tree with example:
If you look closely to above diagram, boundary traversals can be divided into
three essential parts
Print left edge nodes (Excluding leaf nodes)
Print leaf nodes
Print right edge nodes (From bottom to top)
Print left edge nodes (Excluding leaf nodes)

If you define boundary for left part, it is nothing but left child if present,
otherwise right child.
private static void printLeftEdgeNodes(TreeNode root) {

if(root==null)
return;
// if leaf node, ignore while printing edges
if(root.left==null && root.right==null)
return;
System.out.print(root.data+" ");
// If left is null, right will be the boundary edge.
if(root.left==null)
{
printLeftEdgeNodes(root.right);
}
else
{
printLeftEdgeNodes(root.left);
}
}
Print leaf nodes:

Its pretty simple operation. Whenever you encounter leaf node, print it.
private static void printLeafNodes(TreeNode root) {
if(root==null)
return;
{
return;
}
printLeafNodes(root.left);
printLeafNodes(root.right);
}
You may also refer print leaf nodes of binary tree.
Print right edge nodes (From bottom to top) :

If you define boundary for right part, it is nothing but right child if present,
otherwise left child. As we need to print bottom up, we will print the node while
returning back from recursion stack.
private static void printRightBottomUp(TreeNode root)
{
if(root==null)
return;
{
return;
}
if(root.right!=null)
{
printRightBottomUp(root.right);
}
else if(root.left!=null)
{
printRightBottomUp(root.left);
}
}
Complete java program combining above three parts:

{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
public static void boundaryLevelTraversal(TreeNode root)
{
printLeafNodes(root);
}
private static void printLeafNodes(TreeNode root) {
if(root==null)
return;
{
return;
}
printLeafNodes(root.left);
printLeafNodes(root.right);
}
private static void printRightBottomUp(TreeNode root)
{
if(root==null)
return;

{
return;
}
if(root.right!=null)
{
}
else if(root.left!=null)
{
printRightBottomUp(root.left);
}
private static void printLeftEdgeNodes(TreeNode root) {

if(root==null)
return;
return;
// If left is null, right will be the boundary edge.
if(root.left==null)
{
printLeftEdgeNodes(root.right);
}
else
{
}
}
{
System.out.println("Boundary traversal of binary tree will be:");
boundaryLevelTraversal(rootNode);
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
node20.left=node10;
node60.left=node50;
node10.right=node5;
node5.right=node45;
return rootNode;
}
}
When you run above program, you will get below output:
Boundary traversal of binary tree will be:
40 20 10 5 45 30 55 70 60
how to print leaf nodes of a binary tree in java

AlgorithmSteps for counting number of leaf nodes are:
If node is null then return 0
If encounterd leaf node(i.e. node.left is null and node.right is null) then

print the node.
Recursively visit leaf subtree and right subtree.

view plainprint?
1. // print leaf nodes
2. public static void printLeafNodes(TreeNode node) {
3.
4.
if(node==null)
5.
return;
6.
7.
8.
9.
if(node.left == null && node.right == null) {

System.out.printf("%d ",node.data);
}
10. printLeafNodes(node.left);
11. printLeafNodes(node.right);
12.}
Example:
Binary tree:
Lets create java program for counting number of leaf nodes:

view plainprint?
1.
3.
5.
6.
7.
8.
9.
int data;
10. TreeNode left;

11. TreeNode right;
13. {
14.
this.data=data;
15. }
16. }
17.
18. // Recursive Solution
19. // print leaf nodes
20. public static void printLeafNodes(TreeNode node) {
21.
22.
23.
if(node==null)
return;
24.
25.
26.

System.out.printf("%d ",node.data);
27.
28.
printLeafNodes(node.left);
29.
printLeafNodes(node.right);
30. }
31.
32.
33.
35. {
38. System.out.println("Printing leaf nodes in binary tree :");
39. printLeafNodes(rootNode);
40. }
41.
43. {
44.
52.

55.
58.
61.
64.
68. }
69.}
view plainprint?
1.
2. Printing leaf nodes in binary tree :
3. 5 30 55 70
program to count leaf nodes in a binary tree in java

AlgorithmSteps for counting number of leaf nodes are:
If encountered leaf node(i.e. node.left is null and node.right is null) then

return 1.
Recursively calculate number of leaf nodes using

Number of leaf nodes= number of leaf nodes in left subtree + number
of leaf nodes in right sub tree
/* To get the count of leaf nodes in a binary tree*/

public static int getLeafCountOfBinaryTree(TreeNode node)
{
if(node == null)
return 0;
if(node.left ==null && node.right==null)
return 1;
else
return getLeafCountOfBinaryTree(node.left)+
getLeafCountOfBinaryTree(node.right);
}
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
/* To get the count of leaf nodes in a binary tree*/
public static int getLeafCountOfBinaryTree(TreeNode node)
{
if(node == null)
return 0;
if(node.left ==null && node.right==null)
return 1;
else
return getLeafCountOfBinaryTree(node.left)+
getLeafCountOfBinaryTree(node.right);
}
{
System.out.println("Number of leaf nodes in binary
tree :"+getLeafCountOfBinaryTree(rootNode));
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
return rootNode;
}
Number of leaf nodes in binary tree :4
print all paths from root to leaf in a binary tree in java

Below diagram will show all paths from root to leaf:
Algorithm:
Steps for print all paths from root to leaf are:
put node.data in array and increment len by 1.
If encounterd leaf node(i.e. node.left is null and node.right is null) then

print array.
Recursively visit left subtree and right subtree

// Prints all paths to leaf
public static void printAllPathsToLeaf(TreeNode node, int[] path, int
len) {
if ( node == null )
return;
// storing data in array
path[len] = node.data;
len++;
// leaf node is reached
printArray(path,len);
return;
}
printAllPathsToLeaf(node.left, path, len);
printAllPathsToLeaf(node.right, path, len);
}
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// Prints all paths to leaf
public static void printAllPathsToLeaf(TreeNode node, int[] path, int
len) {
if ( node == null )
return;
// storing data in array
path[len] = node.data;
len++;
// leaf node is reached
printArray(path,len);
return;
}
printAllPathsToLeaf(node.left, path, len);

printAllPathsToLeaf(node.right, path, len);
{
System.out.println("Printing all paths from root to leaf :");
printAllPathsToLeaf(rootNode,new int[1000],0);
public static void printArray(int[] path,int len)

{
for (int i = 0; i < len; i++) {
System.out.print(" "+path[i]);
}
System.out.println();
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
node10.left=node5;
return rootNode;
}
}
Printing all paths from root to leaf :

40 20 10 5
40 20 30
40 60 50 55
40 60 70
Find maximum element in binary tree in java
There can be two solutions for it.
Recursive
Iterative
Recursive solution:
Algorithm :
Steps for getting maximum element in binary tree:
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

view plainprint?
1.
2. /* To get max node in a binary tree*/

3. public static int getMaximumRec(TreeNode root)
4. {
5.
int max=Integer.MIN_VALUE;
6.
int value=0;
7.
int left,right;
8.
if(root != null)
9.
10. value=root.data;
11. left=getMaximumRec(root.left);
12. right=getMaximumRec(root.right);
13.
14. if(left>right)
15. {
16.
max=left;
17. }
18. else
19. {
20.
max=right;
21. }
22.
23. if(max < value)
24. {
25.
max=value;
26. }
27. }
28.
29. return max;
30.}
Iterative solution:
Iterative solution will be similar to level order traversal. When we are popping
element from queue, we will check max.
Code for iteration will be :
view plainprint?
1.
// Iterative Solution

3. public static int getMaximumItr(TreeNode startNode) {
4.
5.
6.
7.
int max=Integer.MIN_VALUE;
8.
9.
10. TreeNode tempNode=queue.poll();

11. if(max < tempNode.data)
12.
max=tempNode.data;
13. if(tempNode.left!=null)
14.
15. if(tempNode.right!=null)
16.
17. }
18. return max;
19.}
Lets create java program to get maximum element in binary tree:

Lets say, your binary tree is this:
view plainprint?
2.
3. import java.util.LinkedList;
4. import java.util.Queue;
5.
7.
/*
8.
* @Author : Arpit Mandliya
9.
*/
10.
11. public static class TreeNode
12. {
13. int data;
14. TreeNode left;
15. TreeNode right;
17. {
18.
this.data=data;
19. }
20. }
21.
24. public static int getMaximumRec(TreeNode root)
25. {
26. int max=Integer.MIN_VALUE;
27. int value=0;
28. int left,right;
29. if(root != null)
30. {
31.
value=root.data;
32.
left=getMaximumRec(root.left);
33.
right=getMaximumRec(root.right);
34.
35.
if(left>right)
36.
37.
max=left;
38.
39.
else
40.
41.
42.
max=right;
}
43.
44.
if(max < value)
45.
46.
47.
max=value;
}
48. }
49.
50. return max;
51. }
52.
53. // Iterative Solution
55. public static int getMaximumItr(TreeNode startNode) {
56.
57. Queue<TreeNode> queue=new LinkedList<TreeNode>();
58. queue.add(startNode);
59. int max=Integer.MIN_VALUE;
60. while(!queue.isEmpty())
61. {
62.
63.
if(max < tempNode.data)
64.
max=tempNode.data;
65.
66.
67.
68.
69. }
70. return max;
71. }
72.
73.
75. {
79. System.out.println("Max node using recursion :"+getMaximumRec(root
Node));
80. System.out.println("Max node using iteration :"+getMaximumItr(rootNo
de));
81. }
82.
84. {
85.
93.
96.
99.
100.
node60.left=node50;
101.
102.
103.
104.
105.
return rootNode;
}
}

view plainprint?
1.
2. Max node using recursion :70
3. Max node using iteration :70
Vertical sum of binary tree in java

Below diagram will show vertical sum for binary tree.
Algorithm:
Steps for print vertical sum of binary tree:
Traverse tree in inorder traversal.
Create a variable level and initialise it with 0. When you traverse left
child, decrease level by 1(level--) and when you traverse right child,
increase level by 1(level++).
We need to maintain TreeMap with key as level and value as node

data. If you get same key(level) again, then you need to add current
node data to previous stored value to calculate sum.
For example:
TreeMap has entry with (0,40) where 0 is level and 40 is node data. So
while traversing, if you encountered node 30 at level 0, so after
processing node 30, TreeMap will have entry as (0,70)
Once TreeMap is populated after iterating all nodes, print the results.

// prints vertical sum in binary tree
public static void printVertivalSumOfBinaryTree(TreeNode
startNode,TreeMap<Integer,Integer> treeNodeMap,int level) {
if(startNode==null)
{
return;
}
// Decrease level by 1 when iterating left child
printVertivalSumOfBinaryTree(startNode.left,treeNodeMap,level-1);
if(treeNodeMap.get(level)!=null)
{
// Adding current node data to previous stored value to get the
sum
Integer sum=treeNodeMap.get(level)+startNode.data;
treeNodeMap.put(level, sum);
}
else
{
treeNodeMap.put(level, startNode.data);
}
// Increase level by 1 when iterating left child
printVertivalSumOfBinaryTree(startNode.right,treeNodeMap,level+1);
}
Please find diagram below which shows level assigned for each binary tree
node.
Example:
Lets create java program for printing vertical sum in binary tree:
import java.util.Map.Entry;
import java.util.TreeMap;
public class BinaryTreeVerticalSumMain {
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
// prints vertical sum of binary tree

public static void printVertivalSumOfBinaryTree(TreeNode
startNode,TreeMap<Integer,Integer> treeNodeMap,int level) {
if(startNode==null)
{
return;
}
if(treeNodeMap.get(level)!=null)
{
// Adding current node data to previous stored value to get the sum
}
else
{
}
// Increase level by 1 when iterating left child
printVertivalSumOfBinaryTree(startNode.right,treeNodeMap,level+1);
}
{
BinaryTreeVerticalSumMain bi=new BinaryTreeVerticalSumMain();
System.out.println("Vertical sum of binary tree will be:");
TreeMap<Integer,Integer> treeNodeMap=new TreeMap<Integer,Integer>();
printVertivalSumOfBinaryTree(rootNode, treeNodeMap, 0);
for(Entry<Integer,Integer> entry:treeNodeMap.entrySet())
System.out.println(entry.getValue());
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
node30.left=node5;
return rootNode;
}
Vertical sum of binary tree will be:

10
25
120
115
70
get level of a node in binary tree in java

We will search for a key in binary tree. Root will be at level 1. If we do not find
key in binary tree then its level will be 0.
Algorithm :
Steps for getting level of a node in binary tree:
If node's data is equal to key, then return level.
Recursively search key in left subtree
If not found, then search in right subtree

/* To get level of node in a binary tree*/
public static int getLevelOfNode(TreeNode root,int key,int level)
{
if(root==null)
return 0;
if(root.data==key)
return level;
int result=getLevelOfNode(root.left,key,level+1) ;
if(result!=0)
{
// If found in left subtree , return
return result;
}
result= getLevelOfNode(root.right,key,level+1);
return result;
Lets create java program to get level of node in binary tree:

{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
}
}
//To get level of node in a binary tree
{
if(root==null)
return 0;
if(root.data==key)
return level;
if(result!=0)
{
return result;
}
result= getLevelOfNode(root.right,key,level+1);
return result;
}
{
System.out.println("Node data: 70,Level :"+getLevelOfNode(rootNode, 70,
1));
System.out.println("Node data: 100,Level :"+getLevelOfNode(rootNode,
100, 1));
1));
1));
}
{
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode
TreeNode

node20.left=node10;
node60.left=node50;
return rootNode;
}
}
Node
Node
Node
Node
data:
data:
data:
data:
70,Level :3
100,Level :0
60,Level :2
40,Level :1
get level of a node in binary tree in java

We will search for a key in binary tree. Root will be at level 1. If we do not find
key in binary tree then its level will be 0.
Algorithm :
Steps for getting level of a node in binary tree:
If node's data is equal to key, then return level.
Recursively search key in left subtree
If not found, then search in right subtree

view plainprint?
1. /* To get level of node in a binary tree*/
2.
3.
4.
5.
6.
7.

{
if(root==null)
return 0;
if(root.data==key)
return level;
8.
9.
10. if(result!=0)
11. {
12.
13.
return result;
14.
15. }
16. result= getLevelOfNode(root.right,key,level+1);

17.
18. return result;
19. }
Lets create java program to get level of node in binary tree:
view plainprint?
2.
4.
5.
6.
7.
8.
int data;
9.
TreeNode left;
10. TreeNode right;

12. {
13.
this.data=data;
14. }
15. }
16.
18.//To get level of node in a binary tree
19. public static int getLevelOfNode(TreeNode root,int key,int level)
20. {
21. if(root==null)
22.
return 0;
23. if(root.data==key)
24.
return level;
25.
26. int result=getLevelOfNode(root.left,key,level+1) ;
27. if(result!=0)
28. {
29.
30.
return result;
31. }
32. result= getLevelOfNode(root.right,key,level+1);
33.
34. return result;
35. }
36.
37.
39. {
43. System.out.println("Node data: 70,Level :"+getLevelOfNode(rootNode,
70, 1));
100, 1));
60, 1));
40, 1));
47. }
48.
50. {
51.
59.
62.
65.
68.
70. }
71.}
view plainprint?
1.
2. Node data: 70,Level :3
Lowest Common Ancestor (LCA) of binary tree in java
In this post, we will see how to find lowest common ancestor(LCA) of two nodes
in binary tree. Lets understand with example.
As you can see here, LCA is nothing but lowest common parent of two nodes.
Recursive Algorithm (For nodes A and B):
If node is null, return it
If we find A or B, return it.
Traverse left subtree and right subtree
If we get both left and right for any node as not null, it will be lowest
common ancestor of two given nodes
view plainprint?
1. public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode
a, TreeNode b) {
2.
if(root == null)
3.
return null;
4.
if(root.data == a.data || root.data == b.data )
5.
return root;
6.
7.
TreeNode left=lowestCommonAncestor(root.left,a,b);
8.
TreeNode right=lowestCommonAncestor(root.right,a,b);
9.
10.
// If we get left and right not null , it is lca for a and b
11.
if(left!=null && right!=null)
12.
return root;
13.
if(left== null)
14.
return right;
15.
else
16.
return left;
17.
18.
Complete java program:

view plainprint?
2.
3.
5.
6.
7.
int data;
8.
TreeNode left;
9.
TreeNode right;

11. {
12.
this.data=data;
13. }
14. }
15.
16. public static TreeNode lowestCommonAncestor(TreeNode root, TreeNod
e a, TreeNode b) {
17.
if(root == null)
18.
return null;
19.
if(root.data == a.data || root.data == b.data )
20.
return root;
21.
22.
TreeNode left=lowestCommonAncestor(root.left,a,b);
23.
TreeNode right=lowestCommonAncestor(root.right,a,b);
24.
25.
// If we get left and right not null , it is lca for a and b
26.
if(left!=null && right!=null)
27.
return root;
28.
if(left== null)
29.
return right;
30.
else
31.
return left;
32.
33.

35. {
39. System.out.println("Lowest common ancestor for node 5 and 30:");
42. System.out.println(lowestCommonAncestor(rootNode,node5,node30).d
ata);
43.
44. }
45.
46.
47.
49. {
50.

61.
64.
67.
70.
74. }
75.}
When you run above program, you will get below output:
view plainprint?
1. Lowest common ancestor for node 5 and 30:
2. 20
Vertical sum of binary tree in java

Below diagram will show vertical sum for binary tree.
Algorithm:
Steps for print vertical sum of binary tree:
Traverse tree in inorder traversal.
Create a variable level and initialise it with 0. When you traverse left
child, decrease level by 1(level--) and when you traverse right child,
increase level by 1(level++).
We need to maintain TreeMap with key as level and value as node

data. If you get same key(level) again, then you need to add current
node data to previous stored value to calculate sum.
For example:
TreeMap has entry with (0,40) where 0 is level and 40 is node data. So
while traversing, if you encountered node 30 at level 0, so after
processing node 30, TreeMap will have entry as (0,70)
Once TreeMap is populated after iterating all nodes, print the results.

view plainprint?
1. // prints vertical sum in binary tree
2.
public static void printVertivalSumOfBinaryTree(TreeNode startNode,Tree

Map<Integer,Integer> treeNodeMap,int level) {
3.
if(startNode==null)
4.
5.
6.
return;
}
7.
8.
9.
10.
11. if(treeNodeMap.get(level)!=null)
12. {
13.
14.
15.
16. }
17. else
18. {
19.
20.
21. }
22. // Increase level by 1 when iterating left child
23. printVertivalSumOfBinaryTree(startNode.right,treeNodeMap,level+1);
24.
25. }
Please find diagram below which shows level assigned for each binary tree
node.
Example:
Lets create java program for printing vertical sum in binary tree:
view plainprint?
1.
2.
4.
5. import java.util.Map.Entry;
6. import java.util.TreeMap;
7.
8. public class BinaryTreeVerticalSumMain {
9.
10.
11. public static class TreeNode
12. {
13. int data;
14. TreeNode left;
15. TreeNode right;
17. {
18.
this.data=data;
19. }
20. }
21.
22.// prints vertical sum of binary tree
23. public static void printVertivalSumOfBinaryTree(TreeNode startNode,Tree
Map<Integer,Integer> treeNodeMap,int level) {
24. if(startNode==null)
25. {
26.
return;
27. }
28.
29. // Decrease level by 1 when iterating left child
30. printVertivalSumOfBinaryTree(startNode.left,treeNodeMap,level-1);
31.
32. if(treeNodeMap.get(level)!=null)
33. {
34.
35.
36.
37. }
38. else
39. {
40.
41.
42. }
43. // Increase level by 1 when iterating left child
44. printVertivalSumOfBinaryTree(startNode.right,treeNodeMap,level+1);
45.
46. }
48. {
49. BinaryTreeVerticalSumMain bi=new BinaryTreeVerticalSumMain();

52. System.out.println("Vertical sum of binary tree will be:");
53. TreeMap<Integer,Integer> treeNodeMap=new TreeMap<Integer,Integer
>();
54. printVertivalSumOfBinaryTree(rootNode, treeNodeMap, 0);
55.
56. for(Entry<Integer,Integer> entry:treeNodeMap.entrySet())
57. System.out.println(entry.getValue());
58. }
59.
61. {
62.
72.
75.
78.
84. }
85.}
view plainprint?
1.
2. Vertical sum of binary tree will be:
3. 10
4. 25
5. 120
6. 115
7. 70
8.

Binary Tree in Java

Uploaded by

Copyright:

Available Formats

Binary Tree in Java

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Binary Tree in Java

Uploaded by

Copyright:

Available Formats

Binary tree in java

Binary Tree PreOrder traversal in java

Visit the node.

Traverse the left subtree in PreOrder.

Traverse the right subtree in PreOrder.

There can be two ways of implementing it

Code for recursion will be:

iterative, we will use explicit stack.

Pop a node from stack and print it

Push right child of popped node to stack

Push left child of popped node to stack

Stack<TreeNode> stack = new Stack<TreeNode>();

Lets create java program for PreOrder traversal:

6. public class BinaryTree {

public static class TreeNode

21. public void preorder(TreeNode root) {

//Visit the node-Printing the node data

30. // Iterative solution

Stack<TreeNode> stack = new Stack<TreeNode>();

78. TreeNode node30=new TreeNode(30);

Binary Tree PostOrder traversal in java

Traverse the left subtree in PostOrder.

Traverse the right subtree in PostOrder.

Visit the node.

There can be two ways of implementing it

Code for recursion will be:

1. Create an empty stack s and set currentNode =root.

if( current.right != null && ! s.isEmpty( ) && current.right ==

Lets create java program for InOrder traversal:

rootNode =new TreeNode(40);

Run above program and you will get following output:

Using Recursive solution:

Binary Tree InOrder traversal in java

Traverse the left subtree in InOrder.

Visit the node.

Traverse the right subtree in InOrder.

There can be two ways of implementing it

Code for recursion will be:

//Visit the node by Printing the node data

2. Push the current node to s and set currentNode = currentNode.left until

Pop the top node from stack and print it

Stack<TreeNode> s = new Stack<TreeNode>();

Lets create java program for InOrder traversal:

public static class TreeNode

21. public void inOrder(TreeNode root) {

//Visit the node by Printing the node data

Binary Tree Level Order traversal in java

Pop a node from queue and print it

Push left child of popped node to queue if not null

Push right child of popped node to queue if not null

// prints in level order

So Level Order traversal will work as below:

Lets create java program for level order traversal:

rootNode =new TreeNode(40);

Run above program and you will get following output:

Level Order traversal of binary tree will be:

Spiral/Zigzag level order traversal of binary tree in java

Steps for solution:

// prints in Spiral/Zigzag level order