Write a program to print the Binary tree vertically using the hash table.
Algorithm Explanation
![]() | Build Binary Tree and pass the root node to the utility function. |
![]() | Create the hash map and pass to the utility function. |
![]() | Call recursively with left subtree. If the value is null, create new array list with root key and put in the hash map. Otherwise, add root key to the list. |
![]() | Call recursively with right subtree and print the values. |
Source Code
package com.dsacode.DataStructre.hashtable; import java.util.ArrayList; import java.util.HashMap; class TreeNode { public int key; public TreeNode left; public TreeNode right; public TreeNode(int key) { this.key = key; } } public class PrintBT { public TreeNode root; public void verticalPrint() throws Exception { HashMap < Integer, ArrayList < Integer > > hm= new HashMap < > (); verticalPrintTree(root, 0, hm); System.out.println(hm.entrySet()); } private void verticalPrintTree(TreeNode root, int hd, HashMap < Integer, ArrayList < Integer > > hm) throws Exception { if (root == null) return; verticalPrintTree(root.left, hd - 1, hm); if (hm.get(hd) == null) hm.put(hd, new ArrayList < Integer >(root.key)); else hm.get(hd).add(root.key); verticalPrintTree(root.right, hd + 1, hm); } public void printTree() { printInorder(root); } private void printInorder(TreeNode root) { if (root == null) return; printInorder(root.left); System.out.print(root.key +" "); printInorder(root.right); } public static void main(String[] args) { PrintBT t = new PrintBT(); t.root = new TreeNode(1); t.root.left = new TreeNode(2); t.root.right = new TreeNode(3); t.root.left.left = new TreeNode(4); t.root.left.right = new TreeNode(5); t.root.right.left = new TreeNode(6); t.root.right.right = new TreeNode(7); System.out.print("All the items from the tree:"); t.printTree(); System.out.println(); System.out.print("Print Binary tree items vertically:"); try { t.verticalPrint(); } catch (Exception e) { e.printStackTrace(); } } }
Output
All the items from the tree:4 2 5 1 6 3 7 Print Binary tree items vertically:[-1=[], 0=[1, 6], -2=[], 1=[], 2=[]]