Display nodes of binary tree in a vertical line viewed from top and compute sum of vertical line nodes

Problem:- Display nodes of binary tree in a vertical line viewed from top.
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

9 Comments


  1. If you're interested in experiencing a unique entertainment option, consider attending a ücretli show. These performances offer a variety of captivating acts that can leave you amazed. Whether you're looking for something entertaining for a special occasion or just want to enjoy a night out, a ücretli show can be the perfect choice. Don't miss the opportunity to witness these professional displays of talent.

    ReplyDelete
  2. A new online discovery can be the beginning of useful research. Vaporae is another website to explore if you're interested in the vaping category. Visit the platform to learn about its brand identity, review its online content, and become familiar with its digital presence. Make thoughtful decisions by considering reliable information, health guidance, and applicable local regulations. Start exploring here: https://vaporae.com/

    ReplyDelete
Previous Post Next Post