algorithm to find left view and right view of binary tree in java

This algorithm is an extension of breadth first search. In BFS we just print level wise nodes whereas here while printing level wise nodes we add temporary node in between every level (we can call it is Level_Separator (LS)). Once this is structure is formed then the node before the marker belongs to the right view and the node after the marker belongs to the left view.

What is left view? Nodes which are visible when looking from left. What is right view? Nodes which are visible when looking from right. In a tree like below one

            20
    15              25
      18      22      

Left view nodes are ‘20,15,18’ and right view nodes are ‘20,25,22’

Lets look at an example to understand this algorithm:

            20
    15              25
12      18      22      28

BFS puts this tree in a queue such that all level wise nodes are placed next to each other like this

BFS Queue
	--------------------------------
	20 | 15 | 25 | 12 | 18 | 22 | 28
	--------------------------------

Now add level separator in the above queue

Queue Modified for Left/Right Views
	-----------------------------------------------
	20 | LS | 15 | 25 | LS | 12 | 18 | 22 | 28 | LS
	-----------------------------------------------

Let us take nodes before Level_Separator (LS), i.e, 25,28 and after LS i.e, 15,12 excluding root node.

Now add root node to both before/after LS elements; 20,25,28 and 20,15,12 which are nothing but right view and left view of the binary tree.

	/**
	 * Get left and right view of the binary tree
	 * @param node root of the tree
	 */
	public void printLeftNRightViewOfBT(BinaryNode node) {
		Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
		BinaryNode LS = new BinaryNode(null);
		queue.add(node);
		queue.add(LS);

		// left view and right view arrays
		List<BinaryNode> leftView = new ArrayList<BinaryNode>();
		List<BinaryNode> rightView = new ArrayList<BinaryNode>();
		leftView.add(node);

		while (!queue.isEmpty()) {
			BinaryNode currentNode = queue.remove();
			if (!queue.isEmpty() && currentNode.equals(LS)) {
				leftView.add(queue.peek());
				queue.add(LS);
			}
			if (!queue.isEmpty() && queue.peek().equals(LS)) {
				rightView.add(currentNode);
			}
			if (currentNode.left != null) {
				queue.add(currentNode.left);
			}
			if (currentNode.right != null) {
				queue.add(currentNode.right);
			}
		}

		// print views
		printViews(leftView);
		printViews(rightView);
	}

Output is:

Printing left View: 
50 17 9 14 12 
Printing right view: 
50 76 54 72 67 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey