HashTable

Print Binary Tree vertically

Pinterest LinkedIn Tumblr

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=[]]

Write A Comment