Right View of Binary Tree without Recursion

Imagine you have a binary tree and wants to get all the nodes that will be visible when seen from the right side of the tree. How do you print all such nodes? Final output for this tree should be 44, 51, 65, 26. In other words, the first nodes we touch upon if we draw horizontal lines from right side of the tree. Read on to find the solution.

The Solution

Quicktip, whenever we try to do something without using recursion, you need to use some auxiliary datastructure like Queue or Stack. To solve this problem, we use a queue.

To solve this problem, we use a mechanism similar to Breadth First Traversal

We start with pushing the root node and a null node into queue, to indicate first level is complete. We begin iterating until queue becomes empty. In every iteration, we dequeue a node, if it is not null node, we enqueue its children to the end of queue. We keep adding until children of all the nodes are added to queue.

If we encounter a null node, it means we reached end of the current level. We need to print the node dequeued before this node. To acheive this, we keep checking if next node in the queue is a null node by using peek method. As soon as the peek method returns null, it means this is the last node in the current level, we have to print it. If we get a null node, we have to check if there are more nodes to be dequeued, if there are no more nodes, we have reached end of the binary tree, otherwise, we just reached end of current level and more nodes are present in the queue. Find the program below written in java.

1

Program to print Right View of A 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

public void rightView(Node root) {
    Queue<Node> queue = new Queue<>();
    if(root != null) {
        queue.enqueue(root);
        queue.enqueue(null);  // first level is over
    }

    while (!queue.isEmpty()) {
        Node temp = queue.dequeue();
        if(temp == null) {
            if(queue.getSize() > 0)
                queue.enqueue(null);   // current level is over
            continue;
        }

        if(queue.peek() == null)      // next node is null means end of current level, so print it.
            System.out.println(temp.data);
        if(temp.left != null)
            queue.enqueue(temp.left);
        if(temp.right != null)
            queue.enqueue(temp.right);
    }
}

What do you think of this solution? Can you think of a simpler solution? Let me know in the comments.

SVG for BinaryTree diagram is generated by using Binary Tree Visualizer