Reverse Level Order Traversal
This algorithm is equivalent to breadth-first search traversal in which the nodes at every depth are processed before proceeding to the next level. In this algorithm, all nodes at the same depth are traversed and repeated until the maximum depth of the tree. But in reverse order traversal, the nodes at the maximum depth are processed first and repeated till it reaches the starting depth.
Binary Tree
A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.
class Tree {
public class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
left = right = null;
}
}
In this above tree class with inner node class has one instance member data and two objects of Node class left and right. For every new node, we use Node(int data ) constructor to assign data to that node and set left and right as null.
Tree.Node t = new Tree().new Node(1);
t.left = new Tree().new Node(2);
t.left.left = new Tree().new Node(4);
t.left.right = new Tree().new Node(5);
t.right = new Tree().new Node(3);
Algorithm :
- Create a queue of type node to hold node elements of the tree
- Create a stack of type integer to hold the node data
- Add the root to the queue
- Iterate till queue is empty for every iteration push data to stack and right and left element to queue
Reverse level order traversal: 4 5 2 3 1
public void levelorder(Node root) {
Queue<Node> q = new LinkedList<>();
Stack<Integer> s = new Stack<>();
q.add(root);
while (!q.isEmpty()) {
Node e = q.poll();
s.push(e.data);
if (e.right != null) {
q.offer(e.right);
}
if (e.left != null) {
q.offer(e.left);
}
}
while (!s.isEmpty()) {
System.out.print(s.pop() + " ");
}
}
In the above program, the root is being pushed to the queue and the tree is iterated for the right
and left subtree till the queue is empty. In every iteration, the node data is being pushed to
the stack and the stack is being printed at the end of the program.
I hope you guys liked this article, here are some other articles you may like:
0 Comments