Tutorialspoint.dev

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:

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

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter