Java Program using HashMap:
public class TreeTraversalPrograms { private static Map<Integer, List<TreeNode>> treeNodeVerticalLevelMap = new TreeMap<>(); public static void main(String[] args) { // Tree construction TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); root.right.left.right = new TreeNode(8); root.right.right.right = new TreeNode(9); verticalOrderTraversal(root, 0); SortedSet<Integer> keys = new TreeSet<Integer>(treeNodeVerticalLevelMap.keySet()); for (Integer key : keys) { List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(key); for (TreeNode treeNode : treeNodesList) { System.out.print(treeNode.data + ","); } System.out.println(); } } public static void verticalOrderTraversal(TreeNode node, int width) { if (node == null) { return; } if (treeNodeVerticalLevelMap.containsKey(width)) { List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(width); treeNodesList.add(node); treeNodeVerticalLevelMap.put(width, treeNodesList); } else { List<TreeNode> treeNodesList = new ArrayList<>(); treeNodesList.add(node); treeNodeVerticalLevelMap.put(width, treeNodesList); } if (node.left != null) { verticalOrderTraversal(node.left, width - 1); } if (node.right != null) { verticalOrderTraversal(node.right, width + 1); } } }
Sample Output:
4, 2, 1,5,6, 3,8, 7, 9,
thank u for sharing this post Switching Solutions services
ReplyDeleteSwitching Solutions companies