Tutorialspoint.dev

Vertical width of Binary tree | Set 2

Given a binary tree, find the vertical width of the binary tree. Width of a binary tree is the number of vertical paths.

Examples:

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

Input :
           1
         /    
        2       3
       /      / 
      4   5   6   7
                   
                8   9 
Output : 6

Prerequisite : Print Binary Tree in Vertical order

In this image, the tree contains 6 vertical lines which is the required width of tree.



Approach : In this Approach, we use the approach for printing vertical View of binary tree. Store the horizontal distances in a set and return 1 + highest horizontal distance – lowest horizontal distance. 1 is added to consider horizontal distance 0 as well. While going left, do hd – 1 and for right do hd + 1. We insert all possible distances in a hash table and finally return size of the hash table.

C++

// CPP code to find vertical
// width of a binary tree
#include <bits/stdc++.h>
using namespace std;
  
// Tree class
class Node
{
public :
    int data;
    Node *left, *right;
  
    // Constructor
    Node(int data_new)
    {
        data = data_new;
        left = right = NULL;
    }
};
  
// Function to fill hd in set.
void fillSet(Node* root, unordered_set<int>& s,
                                       int hd)
{
    if (!root)
        return;
  
    fillSet(root->left, s, hd - 1);
    s.insert(hd);
    fillSet(root->right, s, hd + 1);
}
  
int verticalWidth(Node* root)
{
    unordered_set<int> s;
  
    // Third parameter is horizontal
    // distance
    fillSet(root, s, 0);
  
    return s.size();
}
  
int main()
{
    Node* root = NULL;
  
    // Creating the above tree
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->right = new Node(8);
    root->right->right->right = new Node(9);
  
    cout << verticalWidth(root) << " ";
  
    return 0;
}

Python3

# Python code to find vertical
# width of a binary tree

class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None

# Function to fill hd in set.
def fillSet(root, s, hd):
if (not root):
return

fillSet(root.left, s, hd – 1)
s.add(hd)
fillSet(root.right, s, hd + 1)

def verticalWidth(root):
s = set()

# Third parameter is horizontal
# distance
fillSet(root, s, 0)

return len(s)

if __name__ == ‘__main__’:

# Creating the above tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)

print(verticalWidth(root))

# This code is contributed by PranchalK

Output:

6


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter