Home » Binary Tree » Datastructure » Interviews » Reverse Level Order Traversal of Binary Tree in Java

Reverse Level Order Traversal of Binary Tree in Java

in , , - on 19:22:00 - No comments

Reverse Level Order Traversal of Binary Tree in Java 

Print reverse level order traversal of binary tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?
Algorithm
1.  We have already seen how to print nodes at given level. Print Nodes at level K in Binary Tree

 2.  Find the height of the tree and iterate backward from last level to first level printing all nodes at particular level.

3.  Iterate from (treeHeight to 0), call step 1 for printing nodes at each level for each iteration.

Java Program for Reverse Level Order Traversal of Binary Tree.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package com.javabypatel.tree;
 
    /*
    Input:
                     50              Level 0
                  /      \
                 30       70         Level 1
               /   \     /  \
              20   40   60  80       Level 2
             /  \
            10  25                   Level 3
 
    Output: 10 25 20 40 60 80 30 70 50
 
            print nodes at level 3  -> 10 25
            print nodes at level 2  -> 20 40 60 80
            print nodes at level 1  -> 30 70
            print nodes at level 0  -> 50
    */
 
public class ReverseLevelOrderTraversal {
 
    public static void main(String[] args) {
        new ReverseLevelOrderTraversal();
    }
 
    public ReverseLevelOrderTraversal(){
        Node rootNode=null;
        rootNode  = addNode(rootNode, 50);
        rootNode  = addNode(rootNode, 30);
        rootNode  = addNode(rootNode, 70);
        rootNode  = addNode(rootNode, 20);
        rootNode  = addNode(rootNode, 40);
        rootNode  = addNode(rootNode, 10);
        rootNode  = addNode(rootNode, 25);
        rootNode  = addNode(rootNode, 60);
        rootNode  = addNode(rootNode, 80);
 
        reverseLevelOrderTraversal(rootNode);
    }
 
    private int findHeightOfTree(Node rootNode) {
        if(rootNode==null){
            return 0;
        }
 
        int leftHeight = findHeightOfTree(rootNode.getLeft());
        int rightHeight = findHeightOfTree(rootNode.getRight());
 
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
 
    private void reverseLevelOrderTraversal(Node root){
        int height = findHeightOfTree(root);
        for (int level=height-1; level >= 0; level--) {
            printNodesAtLevel(root, level);
        }
    }
 
    private void printNodesAtLevel(Node rootNode, int level) {
        if(rootNode==null){
            return;
        }
 
        if(level == 0){
            System.out.print(rootNode.getData() + " ");
            return;
        }
 
        printNodesAtLevel(rootNode.getLeft(), level - 1);
        printNodesAtLevel(rootNode.getRight(), level - 1);
    }
 
    private Node addNode(Node rootNode, int i) {
        if(rootNode==null){
            return new Node(i);
        }else{
            if(i > rootNode.getData()){
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);
 
            }else{
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}
 
class Node {
    private int data;
    private Node left;
    private Node right;
 
    public Node(int data) {
        this.data = data;
    }
 
    public int getData() {
        return data;
    }
 
    public void setData(int data) {
        this.data = data;
    }
 
    public Node getLeft() {
        return left;
    }
 
    public void setLeft(Node left) {
        this.left = left;
    }
 
    public Node getRight() {
        return right;
    }
 
    public void setRight(Node right) {
        this.right = right;
    }
}

You may also like to see

Level Order Traversal of Binary Tree.

Advanced Multithreading Interview Question-Answer

Traverse a Binary Tree in Level Order Traversal

Serialize and Deserialize a Binary Tree

Find diameter of Binary Tree

How Much Water Can a Bar Graph with different heights can Hold

Interview Question-Answer on Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Categories: , ,