Given a Binary Tree. You need to find and return the vertical width of the tree.
Examples :
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
Output: 6
Explanation: The width of a binary tree is
the number of vertical paths in that tree.
The above tree contains 6 vertical lines.
Input:
1
/ \
2 3
Output: 3
Explanation: The above tree has 3 vertical lines, hence the answer is 3.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(height of the tree).
Constraints:
0 <= number of nodes <= 104
Approach 01:
-
C++
-
Python
class Solution {
public:
int verticalWidth(Node* root) {
if(!root){
return 0;
}
queue<pair<Node*,int>> q;
q.push({root,0});
map<int,int> mp;
while(!q.empty()){
Node* node=q.front().first;
int line=q.front().second;
q.pop();
mp[line]=node->data;
if(node->left){
q.push({node->left,line-1});
}
if(node->right){
q.push({node->right,line+1});
}
}
return mp.size();
}
};
def verticalWidth(root):
if root is None:
return 0
def dfs(node, horizontal_distance, horizontal_distance_set):
if node is None:
return
horizontal_distance_set.add(horizontal_distance)
if node.left:
dfs(node.left, horizontal_distance - 1, horizontal_distance_set)
if node.right:
dfs(node.right, horizontal_distance + 1, horizontal_distance_set)
horizontal_distance_set = set()
dfs(root, 0, horizontal_distance_set)
return len(horizontal_distance_set)