Output:-
Nodes at vertical line
56
11
23 78
12 43 12
18 98
99
Sum at vertical line
Sum at 0 is/are 67
Sum at 1 is/are 116
Sum at 2 is/are 99
Sum at -3 is/are 56
Sum at -2 is/are 11
Sum at -1 is/are 101
Sample code - Order of O(n2 )
// To find min and max horizontal distance. public static void findMinMaxHorizontal(Node root, Values val, int hd) { if (root == null) return; if (hd < val.min) { val.min = hd; } else if (hd > val.max) { val.max = hd; } findMinMaxHorizontal(root.getLeftChild(), val, hd - 1); findMinMaxHorizontal(root.getRightChild(), val, hd + 1); } // order of o(N2) - worst case complexity public static void printVerticalOrderOfON2(Node root) { Values val = new Values(); findMinMaxHorizontal(root, val, 0); // System.out.println(val.min + " " + val.max); for (int i = val.min; i <= val.max; i++) { System.out.println("Nodes in horizontal distance " + i + " is/are "); printVerticalLineNodes(root, i, 0); System.out.println(); } } public static void printVerticalLineNodes(Node root, int line_no, int hd) { if (root == null) return; if (hd == line_no) { System.out.print(root.getData() + " "); } printVerticalLineNodes(root.getLeftChild(), line_no, hd - 1); printVerticalLineNodes(root.getRightChild(), line_no, hd + 1); } class Values { int min; int max; }
Sample code using a HashMap - Order of O(n ), space complexity also O(n)
public static void printVerticalOrderHashMapbased(Node root, Map<Integer, List<Integer>> hmap, int hd) { if (root == null) return; if (hmap.get(hd) == null) { List<Integer> list = new LinkedList<Integer>(); list.add(root.getData()); hmap.put(hd, list); } else { List<Integer> list2 = hmap.get(hd); list2.add(root.getData()); hmap.put(hd, list2); } printVerticalOrderHashMapbased(root.getLeftChild(), hmap, hd - 1); printVerticalOrderHashMapbased(root.getRightChild(), hmap, hd + 1); }
Complete sample program
package com.devinline.trees; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; public class BinaryTreeVerticalSum { // To find min and max horizontal distance. public static void findMinMaxHorizontal(Node root, Values val, int hd) { if (root == null) return; if (hd < val.min) { val.min = hd; } else if (hd > val.max) { val.max = hd; } findMinMaxHorizontal(root.getLeftChild(), val, hd - 1); findMinMaxHorizontal(root.getRightChild(), val, hd + 1); } // order of o(N2) - worst case complexity public static void printVerticalOrderOfON2(Node root) { Values val = new Values(); findMinMaxHorizontal(root, val, 0); // System.out.println(val.min + " " + val.max); for (int i = val.min; i <= val.max; i++) { System.out.println("Nodes in horizontal distance " + i + " is/are "); printVerticalLineNodes(root, i, 0); System.out.println(); } } public static void printVerticalLineNodes(Node root, int line_no, int hd) { if (root == null) return; if (hd == line_no) { System.out.print(root.getData() + " "); } printVerticalLineNodes(root.getLeftChild(), line_no, hd - 1); printVerticalLineNodes(root.getRightChild(), line_no, hd + 1); } public static void printVerticalLineNodesSum(Node root, int hd, Map<Integer, Integer> hmap) { if (root == null) return; int prevSum = hmap.get(hd) == null ? 0 : hmap.get(hd); hmap.put(hd, prevSum + root.getData()); printVerticalLineNodesSum(root.getLeftChild(), hd - 1, hmap); printVerticalLineNodesSum(root.getRightChild(), hd + 1, hmap); } public static void printVerticalOrderHashMapbased(Node root, Map<Integer, List<Integer>> hmap, int hd) { if (root == null) return; if (hmap.get(hd) == null) { List<Integer> list = new LinkedList<Integer>(); list.add(root.getData()); hmap.put(hd, list); } else { List<Integer> list2 = hmap.get(hd); list2.add(root.getData()); hmap.put(hd, list2); } printVerticalOrderHashMapbased(root.getLeftChild(), hmap, hd - 1); printVerticalOrderHashMapbased(root.getRightChild(), hmap, hd + 1); } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); Node root = bt.createTree(); System.out .println("\n====Print vertical elemets of order O(n2)==="); printVerticalOrderOfON2(root); Map<Integer, List<Integer>> hmap2 = new HashMap<>(); System.out .println("\n====Print vertical elemets using hashmap of order O(n)==="); printVerticalOrderHashMapbased(root, hmap2, 0); System.out.println(hmap2.entrySet()); for (int i : hmap2.keySet()) { System.out.println("Nodes with horizontal distance " + i + " is/are " + hmap2.get(i)); } Map<Integer, Integer> hmap = new HashMap<>(); printVerticalLineNodesSum(root, 0, hmap); System.out.println("\n===Print sum of vertical elements using hashmap===="); for (int i : hmap.keySet()) { System.out.println("Sum of nodes at horizontal distance " + i + " is/are " + hmap.get(i)); } } } class Values { int min; int max; } class BinaryTree { Node root; public BinaryTree() { root = null; } public Node createTree() { if (root == null) { root = new Node(12); } root.setLeftChild(new Node(23)); root.setRightChild(new Node(18)); root.getLeftChild().setLeftChild(new Node(11)); root.getLeftChild().setRightChild(new Node(43)); root.getRightChild().setLeftChild(new Node(12)); root.getLeftChild().getLeftChild().setLeftChild(new Node(56)); root.getLeftChild().getLeftChild().setRightChild(new Node(78)); root.getRightChild().getLeftChild().setRightChild(new Node(98)); root.getRightChild().setRightChild(new Node(99)); return root; } } class Node { private int data; private Node leftChild; private Node rightChild; public Node(int data) { this.data = data; leftChild = null; rightChild = null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } }
Sample output:-
====Print vertical elemets of order O(n2)===
Nodes in horizontal distance -3 is/are
56
Nodes in horizontal distance -2 is/are
11
Nodes in horizontal distance -1 is/are
23 78
Nodes in horizontal distance 0 is/are
12 43 12
Nodes in horizontal distance 1 is/are
18 98
Nodes in horizontal distance 2 is/are
99
====Print vertical elemets using hashmap of order O(n)===
[0=[12, 43, 12], 1=[18, 98], 2=[99], -3=[56], -2=[11], -1=[23, 78]]
Nodes with horizontal distance 0 is/are [12, 43, 12]
Nodes with horizontal distance 1 is/are [18, 98]
Nodes with horizontal distance 2 is/are [99]
Nodes with horizontal distance -3 is/are [56]
Nodes with horizontal distance -2 is/are [11]
Nodes with horizontal distance -1 is/are [23, 78]
===Print sum of vertical elements using hashmap====
Sum of nodes at horizontal distance 0 is/are 67
Sum of nodes at horizontal distance 1 is/are 116
Sum of nodes at horizontal distance 2 is/are 99
Sum of nodes at horizontal distance -3 is/are 56
Sum of nodes at horizontal distance -2 is/are 11
Sum of nodes at horizontal distance -1 is/are 101
0 comments:
Post a Comment