Table Of Contents
show
Problem Statement
Given a binary tree, print it vertically.
Sample Test Cases
Input 1:
Output 1:
4
2
1 5 6
3 8
7
9
Explanation 1:
The diagram shows how the vertical traversal of the tree is calculated.
Naive Approach
The naive idea is to find the maximum and minimum horizontal distances with respect to the root of the graph. After we have the range [min, max], we iterate over all the lines from the minimum to the maximum(refer to diagram above) and print the nodes lying on those lines in order. The traversal on the tree can be done recursively as follows for the horizontal distances.
- function(root.left, distance – 1)
- function(root.right, distance + 1)
At each step of recursion, we take the maximum and minimum of the distance.
C++ Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void distanceRoot(TreeNode * root, int & low, int & high, int horDist) {
if (root == NULL) {
return;
}
low = min(low, horDist);
high = max(high, horDist);
distanceRoot(root -> left, low, high, horDist - 1);
distanceRoot(root -> right, low, high, horDist + 1);
}
void getFromLine(TreeNode * root, int num, int horDist, vector < int > & line) {
if (root == NULL) {
return;
}
if (horDist == num) {
line.push_back(root -> val);
}
getFromLine(root -> left, num, horDist - 1, line);
getFromLine(root -> right, num, horDist + 1, line);
}
vector < vector < int >> verticalTraversal(TreeNode * root) {
vector < vector < int >> result;
int low = 0, high = 0;
distanceRoot(root, low, high, 0);
for (int i = low; i <= high; i++) {
vector < int > line;
getFromLine(root, i, 0, line);
result.push_back(line);
}
return result;
}
};
Java Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void distanceRoot(TreeNode root, int[] low, int[] high, int horDist) {
if (root == null) {
return;
}
low[0] = Math.min(low[0], horDist);
high[0] = Math.max(high[0], horDist);
distanceRoot(root.left, low, high, horDist - 1);
distanceRoot(root.right, low, high, horDist + 1);
}
public void getFromLine(TreeNode root, int num, int horDist, List < Integer > line[]) {
if (root == null) {
return;
}
if (horDist == num) {
line[0].add(root.val);
}
getFromLine(root.left, num, horDist - 1, line);
getFromLine(root.right, num, horDist + 1, line);
}
public List < List < Integer >> verticalTraversal(TreeNode root) {
List < List < Integer >> result = new ArrayList < > ();
int[] low = new int[1];
int[] high = new int[1];
distanceRoot(root, low, high, 0);
for (int i = low[0]; i <= high[0]; i++) {
List < Integer > line[] = new ArrayList[1];
line[0] = new ArrayList < Integer > ();
getFromLine(root, i, 0, line);
result.add(line[0]);
}
return result;
}
}
Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def distanceRoot(self, root, low, high, horDist):
if not root:
return
low[0] = min(low[0], horDist)
high[0] = max(high[0], horDist)
self.distanceRoot(root.left, low, high, horDist - 1)
self.distanceRoot(root.right, low, high, horDist + 1)
def getFromLine(self, root, num, horDist, line):
if not root:
return
if horDist == num:
line.append(root.val)
self.getFromLine(root.left, num, horDist - 1, line)
self.getFromLine(root.right, num, horDist + 1, line)
def verticalTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
low = [0]
high = [0]
result = []
self.distanceRoot(root, low, high, 0)
for i in range(low[0], high[0] + 1):
line = []
self.getFromLine(root, i, 0, line)
result.append(line)
return result
Complexity Analysis
- Time Complexity: O(n * n)
- Space Complexity: O(n)
Approach 2 (HashMap Based Approach)
We can optimize the above naive approach by using a hashmap. Observe that all nodes which have the same horizontal distance from the root, lie on the same vertical line. So, by making the horizontal distances the key of the map, we can recursively push the nodes, into the proper key container while calculating the horizontal distances in the same recursive calls themselves.
The algorithm is as follows:
- Initialize a Map with [Key, Value] pair as [Integer, Vector<Integer>].
- Recursively traverse on the tree (both left and right child) keeping track of the horizontal distances with respect to the root node.
- With the current horizontal distance as the key, push the current node, into the map of vectors.
- Once the recursion terminates, we store each of the values(vectors) in the map, for distinct keys, and return them.
The thing to note about this approach is that it may not print the nodes in the same vertical order in which they appear in the tree.
C++ Implementation
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void getVerticalTraversal(TreeNode * root, int horDist, map < int, vector < int >> & m) {
if (root == NULL) {
return;
}
m[horDist].push_back(root -> val);
getVerticalTraversal(root -> left, horDist - 1, m);
getVerticalTraversal(root -> right, horDist + 1, m);
}
vector < vector < int >> verticalTraversal(TreeNode * root) {
map < int, vector < int >> m;
getVerticalTraversal(root, 0, m);
vector < vector < int >> result;
for (auto x: m) {
result.push_back(x.second);
}
return result;
}
};
Java Implementation
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void getFromLine(TreeNode root, int num, int horDist, List < Integer > line[]) {
if (root == null) {
return;
}
if (horDist == num) {
line[0].add(root.val);
}
getFromLine(root.left, num, horDist - 1, line);
getFromLine(root.right, num, horDist + 1, line);
}
public List < List < Integer >> verticalTraversal(TreeNode root) {
List < List < Integer >> result = new ArrayList < > ();
int[] low = new int[1];
int[] high = new int[1];
distanceRoot(root, low, high, 0);
for (int i = low[0]; i <= high[0]; i++) {
List < Integer > line[] = new ArrayList[1];
line[0] = new ArrayList < Integer > ();
getFromLine(root, i, 0, line);
result.add(line[0]);
}
return result;
}
}
Python Implementation
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def getVerticalTraversal(self, root, horDist, m):
if not root:
return
try:
m[horDist].append(root.val)
except:
m[horDist] = [root.val]
self.getVerticalTraversal(root.left, horDist - 1, m)
self.getVerticalTraversal(root.right, horDist + 1, m)
def verticalTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
m = dict()
self.getVerticalTraversal(root, 0, m)
for res in sorted(m.keys()):
result.append(m[res])
return result
Complexity Analysis:
- Time Complexity: O(n * logn) or O(n) depending on the type of map used.
- Space Complexity: O(n)
Approach 3 (BFS Based Approach)
To solve the issue of the nodes not coming in order, we can use a level order traversal-based approach on this tree. Using level order traversal ensures that a node that is below another node in the same vertical line, comes after that node when the results are being printed. The algorithm is described as follows:
- Declare a map for branches of each node.
- Start a BFS or level order traversal from each node.
- Initialize a queue, which holds the following information, the data of the node and its horizontal distance from the root (can also be identified as its line number).
- Now while the queue is not emptied, do the following,
- Take the top element from the queue, pop it, and add its data in the corresponding branch’s vector.
- If the left child of the node is not null, push it into the queue, with branch number as current branch number – 1.
- If the right child of the node is not null, push it into the queue, with branch number as current branch number + 1.
- Print/Return the values from the map accordingly in proper order.
C++ Code For BFS Approach
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void getTraversal(TreeNode * root, vector < vector < int >> & res) {
if (root == NULL) {
return;
}
int horDist = 0;
map < int, vector < int >> m;
queue < pair < TreeNode * , int >> q;
q.push({
root,
horDist
});
while (!q.empty()) {
auto x = q.front();
q.pop();
TreeNode * u = x.first;
horDist = x.second;
m[horDist].push_back(u -> val);
if (u -> left != NULL) {
q.push({
u -> left,
horDist - 1
});
}
if (u -> right != NULL) {
q.push({
u -> right,
horDist + 1
});
}
}
for (auto x: m) {
res.push_back(x.second);
}
}
vector < vector < int >> verticalTraversal(TreeNode * root) {
vector < vector < int >> result;
getTraversal(root, result);
return result;
}
};
Java Code For BFS Approach
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Q_pair {
int hor_dist;
TreeNode node;
Q_pair(int hor_dist, TreeNode node) {
this.hor_dist = hor_dist;
this.node = node;
}
}
class Solution {
public List < List < Integer >> verticalTraversal(TreeNode root) {
List < List < Integer >> result = new ArrayList < > ();
if (root == null)
return result;
TreeMap < Integer, List < Integer > > map = new TreeMap < > ();
int hor_d = 0;
Queue < Q_pair > q = new LinkedList < > ();
q.add(new Q_pair(0, root));
while (!q.isEmpty()) {
Q_pair temp = q.poll();
hor_d = temp.hor_dist;
TreeNode node = temp.node;
if (map.containsKey(hor_d)) {
map.get(hor_d).add(node.val);
} else {
List < Integer > arr = new ArrayList < > ();
arr.add(node.val);
map.put(hor_d, arr);
}
if (node.left != null)
q.add(new Q_pair(hor_d - 1, node.left));
if (node.right != null)
q.add(new Q_pair(hor_d + 1, node.right));
}
for (Map.Entry < Integer, List < Integer > > entry: map.entrySet()) {
result.add(entry.getValue());
}
return result;
}
}
Python Code For BFS Approach
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def traverse(self, root, res):
if not root:
return
queue = []
m = {}
horDistm = {}
queue.append(root)
horDistm[root] = 0
m[0] = [root.val]
while len(queue) > 0:
u = queue.pop(0)
if u.left:
queue.append(u.left)
horDistm[u.left] = horDistm[u] - 1
horDist = horDistm[u.left]
if m.get(horDist) is None:
m[horDist] = []
m[horDist].append(u.left.val)
else:
m[horDist].append(u.left.val)
if u.right:
queue.append(u.right)
horDistm[u.right] = horDistm[u] + 1
horDist = horDistm[u.right]
if m.get(horDist) is None:
m[horDist] = []
m[horDist].append(u.right.val)
else:
m[horDist].append(u.right.val)
m_ = collections.OrderedDict(sorted(m.items()))
for i in m_.values():
res.append(i)
def verticalTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.traverse(root, res)
return res
Complexity Analysis:
- Time Complexity: O(n * logn) or O(n) depending on the type of map used.
- Space Complexity: O(n)
Practice Problem
FAQs
Q. How does the type of map determine the time complexity of the programs?
A. Different maps are implemented internally in different manners. Some are implemented using hashing, taking up constant lookup times, while others are implemented using AVL or Red-Black Trees which take up a logarithmic factor for lookups and updates.
Q. What are the different ways of traversing a binary tree?
A. There are different ways of traversing a binary tree such as Preorder Traversal, Postorder Traversal, Level Order Traversal, etc.
