# Vertical width of Binary tree | Set 1

Given a binary tree, find the vertical width of the binary tree. The width of a binary tree is the number of vertical paths. In this image, the tree contains 6 vertical lines which are the required width of the tree.

Examples :

```Input :
7
/
6    5
/   /
4   3 2  1
Output :
5

Input :
1
/
2       3
/      /
4   5   6   7

8   9
Output :
6
```

Approach : Take inorder traversal and then take a temporary variable if we go left then temp value decreases and if go to right then temp value increases. Assert a condition in this, if the minimum is greater than temp, then minimum = temp and if maximum less then temp then maximum = temp. In the end, print minimum + maximum which is the vertical width of the tree.

## C++

 `// CPP program to print vertical width ` `// of a tree ` `#include ` `using` `namespace` `std; ` ` `  `// A Binary Tree Node ` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *left, *right; ` `}; ` ` `  `// get vertical width ` `void` `lengthUtil(Node* root, ``int` `&maximum, ` `                ``int` `&minimum, ``int` `curr=0) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``// traverse left ` `    ``lengthUtil(root->left, maximum, ` `               ``minimum, curr - 1); ` ` `  `    ``// if curr is decrease then get ` `    ``// value in minimum ` `    ``if` `(minimum > curr) ` `        ``minimum = curr; ` ` `  `    ``// if curr is increase then get ` `    ``// value in maximum ` `    ``if` `(maximum < curr) ` `        ``maximum = curr; ` ` `  ` `  `    ``// traverse right ` `    ``lengthUtil(root->right, maximum, ` `               ``minimum,  curr + 1); ` ` `  `} ` ` `  `int` `getLength(Node* root) ` `{ ` `    ``int` `maximum = 0, minimum = 0; ` `    ``lengthUtil(root, maximum, minimum, 0); ` ` `  `    ``// 1 is added to include root in the width ` `    ``return` `(``abs``(minimum) + maximum) + 1; ` `} ` ` `  `// Utility function to create a new tree node ` `Node* newNode(``int` `data) ` `{ ` `    ``Node* curr = ``new` `Node; ` `    ``curr->data = data; ` `    ``curr->left = curr->right = NULL; ` `    ``return` `curr; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` ` `  `    ``Node* root = newNode(7); ` `    ``root->left = newNode(6); ` `    ``root->right = newNode(5); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(3); ` `    ``root->right->left = newNode(2); ` `    ``root->right->right = newNode(1); ` ` `  `    ``cout << getLength(root) << ````" "````; ` ` `  `    ``return` `0; ` `} `

## Python3

# Python3 program to prvertical width
# of a tree

# class to create a new tree node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None

# get vertical width
def lengthUtil(root, maximum, minimum, curr = 0):
if (root == None):
return

# traverse left
lengthUtil(root.left, maximum,
minimum, curr – 1)

# if curr is decrease then get
# value in minimum
if (minimum > curr):
minimum = curr

# if curr is increase then get
# value in maximum
if (maximum < curr): maximum = curr # traverse right lengthUtil(root.right, maximum, minimum, curr + 1) def getLength(root): maximum =  minimum =  lengthUtil(root, maximum, minimum, 0) # 1 is added to include root in the width return (abs(minimum) + maximum) + 1 # Driver Code if __name__ == '__main__': root = newNode(7) root.left = newNode(6) root.right = newNode(5) root.left.left = newNode(4) root.left.right = newNode(3) root.right.left = newNode(2) root.right.right = newNode(1) print(getLength(root)) # This code is contributed by PranchalK [tabbyending]

Output:

```5
```

Time Complexity: O(n)
Auxiliary Space: O(h) where h is the height of the binary tree. This much space is needed for recursive calls.

This article is attributed to GeeksforGeeks.org

code

load comments