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 <bits/stdc++.h> 
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[0] > curr):
minimum[0] = curr

# if curr is increase then get
# value in maximum
if (maximum[0] < curr): maximum[0] = curr # traverse right lengthUtil(root.right, maximum, minimum, curr + 1) def getLength(root): maximum = [0] minimum = [0] lengthUtil(root, maximum, minimum, 0) # 1 is added to include root in the width return (abs(minimum[0]) + maximum[0]) + 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:

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.

Vertical width of Binary tree | Set 1

C++

Python3

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books