Given a binary tree, print it vertically.
NOTE: If there are multiple nodes at the same point, then print them in sorted order.
Examples:
Input: 1
/ \
2 3
/ \ / \
4 11 6 7
/ \
8 9
Output: [ [4], [2], [1, 6, 11], [3, 8], [7], [9] ]
Explanation: Traversing the tree vertically gives the above output.Input: 5
/ \
4 6
/ \ /
3 1 2
Output: [ [3], [4], [1, 2, 5], [6] ]
Approach: This problem is similar to Print a Binary Tree in Vertical Order. In that problem, if there are 2 nodes on the same vertical and on the same level then it is required to print from left to right, but this problem requires printing it in the sorted order. For that, take queue and map which consists of pair of integer and multiset to store multiple nodes that can have the same value as well.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Structure for a binary tree nodestruct Node { int key; Node *left, *right;};// A utility function to create a new nodestruct Node* newNode(int key){ struct Node* node = new Node; node->key = key; node->left = node->right = NULL; return node;}// Function to print vertical traversal // of a binary treevector<vector<int> > printVerticalOrder(Node* root){ // map<vertical, map<level, // multiset<node values> > > map<int, map<int, multiset<int> > > mpp; // queue<Nodes, vertical, level> queue<pair<Node*, pair<int, int> > > q; q.push({ root, { 0, 0 } }); while (!q.empty()) { auto p = q.front(); q.pop(); Node* temp = p.first; // Vertical int vertical = p.second.first; // Level int level = p.second.second; // 2,0 -> {5,6} insert in the multiset mpp[vertical][level].insert(temp->key); // If left child of the node exits // then push it on the queue // with vertical decremented and // level incremented if (temp->left) q.push({ temp->left, { vertical - 1, level + 1 } }); // If right child of the node exits // then push it on the queue // with vertical incremented and // level incremented if (temp->right) q.push({ temp->right, { vertical + 1, level + 1 } }); } vector<vector<int> > ans; // Traverse the multiset part of each map for (auto p : mpp) { vector<int> col; for (auto q : p.second) { col.insert(col.end(), q.second.begin(), q.second.end()); } ans.push_back(col); } return ans;}// Driver Codeint main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(11); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); root->right->right->right = newNode(9); // To store the vertical order traversal vector<vector<int> > v = printVerticalOrder(root); for (auto i : v) { for (auto j : i) { cout << j << " "; } cout << endl; } return 0;} |
Java
//java program for above approachimport java.util.*;// Structure for a binary tree nodeclass Node { int key; Node left, right; Node(int data) { key = data; left = right = null; }}//custom pair classclass Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } public void setKey(K key) { this.key = key; } public void setValue(V value) { this.value = value; }}class Main { // Function to print vertical traversal // of a binary tree public static List<List<Integer> > printVerticalOrder(Node root) { // map<vertical, map<level, // multiset<node values> > > Map<Integer, Map<Integer, TreeSet<Integer> > > map = new TreeMap<>(); // queue<Nodes, vertical, level> Queue<Pair<Node, Pair<Integer, Integer> > > q = new LinkedList<>(); List<List<Integer> > res = new ArrayList<>(); if (root == null) return res; q.add(new Pair<>(root, new Pair<>(0, 0))); while (!q.isEmpty()) { Pair<Node, Pair<Integer, Integer> > p = q.peek(); q.remove(); Node temp = p.getKey(); int vertical = p.getValue().getKey(); int level = p.getValue().getValue(); if (!map.containsKey(vertical)) map.put(vertical, new TreeMap<>()); if (!map.get(vertical).containsKey(level)) map.get(vertical).put(level, new TreeSet<>()); map.get(vertical).get(level).add(temp.key); // If left child of the node exits // then push it on the queue // with vertical decremented and // level incremented if (temp.left != null) q.add(new Pair<>( temp.left, new Pair<>(vertical - 1, level + 1))); // If right child of the node exits // then push it on the queue // with vertical incremented and // level incremented if (temp.right != null) q.add(new Pair<>( temp.right, new Pair<>(vertical + 1, level + 1))); } // Traverse the multiset part of each map for (Map.Entry<Integer, Map<Integer, TreeSet<Integer> > > entry : map.entrySet()) { List<Integer> col = new ArrayList<>(); for (Map.Entry<Integer, TreeSet<Integer> > values : entry.getValue().entrySet()) { col.addAll(values.getValue()); } res.add(col); } return res; } // Driver Code public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(11); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(8); root.right.right.right = new Node(9); // To store the vertical order traversal List<List<Integer> > v = printVerticalOrder(root); for (List<Integer> i : v) { for (Integer j : i) { System.out.print(j + " "); } System.out.println(); } }} |
Python3
# Python program for the above approachfrom collections import deque# Structure for a binary tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None# Function to print vertical traversal # of a binary treedef printVerticalOrder(root): # map<vertical, map<level, # multiset<node values> > > mpp = {} # queue<Nodes, vertical, level> q = deque() q.append((root, (0, 0))) while q: temp, (vertical, level) = q.popleft() # 2,0 -> {5,6} insert in the multiset if vertical in mpp: if level in mpp[vertical]: mpp[vertical][level].add(temp.key) else: mpp[vertical][level] = {temp.key} else: mpp[vertical] = {level: {temp.key}} # If left child of the node exits # then push it on the queue # with vertical decremented and # level incremented if temp.left: q.append((temp.left, (vertical - 1, level + 1))) # If right child of the node exits # then push it on the queue # with vertical incremented and # level incremented if temp.right: q.append((temp.right, (vertical + 1, level + 1))) ans = [] # Traverse the multiset part of each map for vertical in sorted(mpp.keys()): col = [] for level in sorted(mpp[vertical].keys()): col.extend(sorted(mpp[vertical][level])) ans.append(col) return ans# Driver Codeif __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(11) root.right.left = Node(6) root.right.right = Node(7) root.right.left.right = Node(8) root.right.right.right = Node(9) # To store the vertical order traversal v = printVerticalOrder(root) for i in v: for j in i: print(j, end=" ") print()# This code is contributed by rishabmalhdjio |
C#
// C# program for the above approachusing System;using System.Collections.Generic;namespace HelloWorld {// Structure for a binary tree nodepublic class Node { public int key; public Node left, right;}public class Program { // A utility function to create a new node public static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return node; } // Function to print vertical traversal // of a binary tree public static List<List<int> > printVerticalOrder(Node root) { // map<vertical, map<level, // multiset<node values> > > SortedDictionary< int, SortedDictionary<int, SortedSet<int> > > mpp = new SortedDictionary< int, SortedDictionary<int, SortedSet<int> > >(); // queue<Nodes, vertical, level> Queue<Tuple<Node, Tuple<int, int> > > q = new Queue<Tuple<Node, Tuple<int, int> > >(); q.Enqueue(new Tuple<Node, Tuple<int, int> >( root, new Tuple<int, int>(0, 0))); while (q.Count > 0) { var p = q.Dequeue(); Node temp = p.Item1; // Vertical int vertical = p.Item2.Item1; // Level int level = p.Item2.Item2; // 2,0 -> {5,6} insert in the multiset if (!mpp.ContainsKey(vertical)) { mpp[vertical] = new SortedDictionary< int, SortedSet<int> >(); } if (!mpp[vertical].ContainsKey(level)) { mpp[vertical][level] = new SortedSet<int>(); } mpp[vertical][level].Add(temp.key); // If left child of the node exits // then push it on the queue // with vertical decremented and // level incremented if (temp.left != null) q.Enqueue(new Tuple<Node, Tuple<int, int> >( temp.left, new Tuple<int, int>(vertical - 1, level + 1))); // If right child of the node exits // then push it on the queue // with vertical incremented and // level incremented if (temp.right != null) q.Enqueue(new Tuple<Node, Tuple<int, int> >( temp.right, new Tuple<int, int>(vertical + 1, level + 1))); } List<List<int> > ans = new List<List<int> >(); // Traverse the multiset part of each map foreach(var p in mpp) { List<int> col = new List<int>(); foreach(var qItem in p.Value) { col.AddRange(qItem.Value); } ans.Add(col); } return ans; } // Driver Code static void Main(string[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(11); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); root.right.right.right = newNode(9); // To store the vertical order traversal List<List<int> > v = printVerticalOrder(root); foreach(var i in v) { foreach(var j in i) { Console.Write(j + " "); } Console.WriteLine(); } }}}// This code is contributed by Chetan Bargal |
Javascript
// JavaScript program for the above approachclass Node { constructor(key) { this.key = key; this.left = null; this.right = null; }}// Function to print vertical traversal// of a binary treefunction printVerticalOrder(root) { // map<vertical, map<level, // multiset<node values> > > let mpp = new Map(); // queue<Nodes, vertical, level> let q = []; q.push([root, [0, 0]]); while (q.length) { let [temp, [vertical, level]] = q.shift(); // 2,0 -> {5,6} insert in the multiset if (mpp.has(vertical)) { if (mpp.get(vertical).has(level)) { mpp.get(vertical).get(level).add(temp.key); } else { mpp.get(vertical).set(level, new Set([temp.key])); } } else { mpp.set(vertical, new Map([ [level, new Set([temp.key])] ])); } // If left child of the node exits // then push it on the queue // with vertical decremented and // level incremented if (temp.left) { q.push([temp.left, [vertical - 1, level + 1]]); } // If right child of the node exits // then push it on the queue // with vertical incremented and // level incremented if (temp.right) { q.push([temp.right, [vertical + 1, level + 1]]); } } let ans = []; // Traverse the multiset part of each map for (let vertical of [...mpp.keys()].sort((a, b) => a - b)) { let col = []; for (let level of [...mpp.get(vertical).keys()].sort((a, b) => a - b)) { col.push(...[...mpp.get(vertical).get(level)].sort((a, b) => a - b)); } ans.push(col); } return ans;}// Driver Codelet root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.left.right = new Node(11);root.right.left = new Node(6);root.right.right = new Node(7);root.right.left.right = new Node(8);root.right.right.right = new Node(9);// To store the vertical order traversallet v = printVerticalOrder(root);for (let i of v) { console.log(i.join(" "));} |
Output
4 2 1 6 11 3 8 7 9
Time Complexity: O(N*logN*logN*logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
