import java.util.Queue;
import java.util.LinkedList;
class LevelOrderTreeTraversal {
private static Node root;
void leverOrderUsingQueue(Node root) {
if(root == null) {
return;
}
Queue queue = new LinkedList<>();
queue.add(root);
Node current;
while(!queue.isEmpty()) {
// dequeue from queue
current = queue.poll();
System.out.print(current.data + " ");
// enqueue left node
if(current.left != null) {
queue.add(current.left);
}
// enqueue right node
if(current.right != null) {
queue.add(current.right);
}
}
}
/**
* Time to print n levels is O(n^2)
*/
void leverOrderUsingRecursion(Node root) {
if(root == null) {
return;
}
int height = height(root);
for(int i = 0; i <= height; i++) {
printLevel(root, i);
System.out.println();
}
}
/**
* Time to print level is O(n)
*/
void printLevel(Node root, int level) {
// return if null
if(root == null) {
return;
}
if(level == 0) {
System.out.print(root.data + " ");
return;
} else if(level > 0) {
printLevel(root.left, level - 1);
printLevel(root.right, level - 1);
}
}
Node populateTree() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
return root;
}
int height(Node root) {
// height starts from 0 and lever starts from 1
if(root == null) {
return -1;
}
// calculate height of left and right sub trees
int lHeight = height(root.left);
int rHeight = height(root.right);
// return larger height
return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
public static void main (String[] args) {
LevelOrderTreeTraversal tree = new LevelOrderTreeTraversal();
root = tree.populateTree();
System.out.println("Lever order traversal using queue :");
tree.leverOrderUsingQueue(root);
System.out.println("\nLevel order traversal using recursion :");
tree.leverOrderUsingRecursion(root);
System.out.println("\nHeight of tree : " + tree.height(root));
}
private static class Node {
Node left;
int data;
Node right;
public Node(int data) {
this.data = data;
}
}
}
Output
Lever order traversal using queue :
1 2 3 4 5 6 7
Level order traversal using recursion :
1
2 3
4 5 6 7
Height of tree : 2
Comments
Post a Comment