Site icon

Print vertical order traversal of binary tree in java (recursive & example)

Example 1: find vertical distance of nodes in binary tree using java

Fig 1: Vertical order traversal

Example 2: Vertical order distance of binary tree in java

Fig 2: Vertical order traversal

Algorithm to find vertical distance in a binary tree using java

Fig 3: Vertical distance binary tree

Time complexity of algorithm is O(n).

Program – Vertical order traversal of a binary tree (recursive) using java

1.) VerticalOrderOfBTree class:

package org.learn.Question;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class VerticalOrderOfBTree {
	private static Map<Integer, List<Integer>> mapVerticalDistance = null;

	private static void verticalOrder(Node root, int distance) {
		if (null == root)
			return;

		List<Integer> list = null;
		if (mapVerticalDistance.containsKey(distance)) {
			list = mapVerticalDistance.get(distance);
		} else {
			list = new ArrayList<Integer>();
		}
		
		list.add(root.data);
		mapVerticalDistance.put(distance, list);
		verticalOrder(root.left, distance - 1);
		verticalOrder(root.right, distance + 1);
	}

	public static void verticalOrderOfBTree(Node root) {
		
		if (null == mapVerticalDistance) {
			mapVerticalDistance = new HashMap<Integer, List<Integer>>();
		} else {
			mapVerticalDistance.clear();
		}
		
		verticalOrder(root, 0);
		mapVerticalDistance
				.forEach(
						(k, v) 
							-> System.out.println("Nodes at distance " + k + " = " + v));
	}
}

2.) Node Class:

package org.learn.Question;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.VerticalOrderOfBTree;

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(50);
		// Level 1
		Node B = Node.createNode(25);
		Node C = Node.createNode(75);
		// Level 2
		Node D = Node.createNode(10);
		Node E = Node.createNode(40);
		Node F = Node.createNode(60);
		Node G = Node.createNode(90);

		// connect Level 0 and 1
		A.left = B;
		A.right = C;
		// connect level 1 and level 2
		B.left = D;
		B.right = E;
		C.left = F;
		C.right = G;

		VerticalOrderOfBTree.verticalOrderOfBTree(A);
	}
}

Output – vertical order traversal of binary tree using java

Nodes at distance 0 = [50, 40, 60]
Nodes at distance -1 = [25]
Nodes at distance -2 = [10]
Nodes at distance 1 = [75]
Nodes at distance 2 = [90]

Download Code – print binary tree in Vertical Order (DFS)

 

Exit mobile version