Maximum width of a binary tree

Question: Given a binary tree, write a function to get the maximum width of the given tree. Width of a tree is maximum widths of all levels.

Let us consider the below example tree.

        1
        /  \
       2    3
     /  \     \
    4    5     8
              /  \
             6    7

For the above tree,

width of level 1 is 1,

width of level 2 is 2,

width of level 3 is 3

width of level 4 is 2.

So the maximum width of the tree is 3.

Solution:

Method 1 (Using Level Order Traversal)

This method mainly involves two functions. One is to count nodes at a given level (getWidth), and other is to get the maximum width of the tree(getMaxWidth). getMaxWidth() makes use of getWidth() to get the width of all levels starting from root.

/*Function to print level order traversal of tree*/
getMaxWidth(tree)
maxWdth = 0
for i = 1 to height(tree)
  width =   getWidth(tree, i);
  if(width > maxWdth)
      maxWdth  = width
return width

/*Function to get width of a given level */
getWidth(tree, level)
if tree is NULL then return 0;
if level is 1, then return 1; 
else if level greater than 1, then
    return getWidth(tree->left, level-1) +
    getWidth(tree->right, level-1);

-----------------
Code in Java:
-----------------
   public int height(TreeNode T) {
        if(T==null)
            return 0;
        return Math.max(height(T.left),height(T.right))+1;
    }
    
    public int getMaxWidth(TreeNode root) {
        int maxWidth=0;
        int height = height(root);
        for(int i=1; i<=height; i++) {
            int width=getWidth(root, i);
            if(width>maxWidth) {
                maxWidth=width;
            }
        }
        return maxWidth;
    }
    
    public int getWidth(TreeNode T, int level) {
        if(T==null) 
            return 0;
        if(level==1)
            return 1;
        else 
            return getWidth(T.left, level-1)+getWidth(T.right, level-1);

    }

Method 2 (Using Preorder Traversal)

In this method we create a temporary array count[] of size equal to the height of tree. We initialize all values in count as 0. We traverse the tree using preorder traversal and fill the entries in count so that the count array contains count of nodes at each level in Binary Tree.

/* Function to get the maximum width of a binary tree*/

int getMaxWidth(struct node* root)

{

  int width;

  int h = height(root);

  // Create an array that will store count of nodes at each level

  int *count = (int *)calloc(sizeof(int), h);

  int level = 0;

  // Fill the count array using preorder traversal

  getMaxWidthRecur(root, count, level);

  // Return the maximum value from count array

  return getMax(count, h);

}

// A function that fills count array with count of nodes at every

// level of given binary tree

void getMaxWidthRecur(struct node *root, int count[], int level)

{

  if(root)

  {

    count[level]++;

    getMaxWidthRecur(root->left, count, level+1);

    getMaxWidthRecur(root->right, count, level+1);

  }

}

Diameter of a Binary Tree

Question: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

Solution:

public int getHeight(Node root) 
{
if (root == null) 
        return 0;
    return Math.max(getHeight(root.left), getHeight(root.right))+1;
}

public int Diameter(Node root) {
if (root == null) 
      return 0;

// get the left and right subtree height
int leftSubTree = getHeight(root.left);
int rightSubTree = getHeight(root.right);

// get the left diameter and right diameter recursively.
int leftDiameter = Diameter(root.left);
int rightDiameter = Diameter(root.right);

// get the max leftsubtree, rightsubtree, longest path goes through root.
return Math.max(leftSubTree+rightSubTree+1, Math.max(leftDiameter, rightDiameter));
}

Solution 2:

/*The second parameter is to store the height of tree.    Initially, we need to pass a pointer to a location with value    as 0. So, function should be used as follows:    int height = 0;    struct node *root = SomeFunctionToMakeTree();    int diameter = diameterOpt(root, &height); */ int diameterOpt(struct node *root, int* height) {   /* lh --> Height of left subtree       rh --> Height of right subtree */   int lh = 0, rh = 0;     /* ldiameter  --> diameter of left subtree       rdiameter  --> Diameter of right subtree */   int ldiameter = 0, rdiameter = 0;     if(root == NULL)   {     *height = 0;      return 0; /* diameter is also 0 */   }     /* Get the heights of left and right subtrees in lh and rh     And store the returned values in ldiameter and ldiameter */   ldiameter = diameterOpt(root->left, &lh);   rdiameter = diameterOpt(root->right, &rh);     /* Height of current node is max of heights of left and      right subtrees plus 1*/   *height = max(lh, rh) + 1;     return max(lh + rh + 1, max(ldiameter, rdiameter)); }

Time Complexity: O(n)

Kth largest number in BST

Question: Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

For example, in the following BST, if k = 3, then output should be 14, and if k = 5, then output should be 10.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Public void kthLargest(TreeNode T, int k, int count) { if(T=!NULL) { kthLargest(T.right, k, count); count++; if(count == k) { System.out.println(T.element); return; } kthLargest(T.left, k, count); } }

Majority Element

Question: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Algo:
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

Step#1:
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count–;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Step#2:
Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print “NONE”

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

int findMajority(int[] a)     {         int count, major;               count=0;         major=0;                for(int i=0; i<a.length; i++){             if(count==0){                 major=a[i];                 count=1;             }             else if(a[i] == major){                 count++;             }             else{                 count--;             }         }               return major;     }           boolean isMajority(int[] a, int majNum) {                   int count=0, size=a.length;         for(int i=0; i<size; i++) {             if(a[i]==majNum) {                 count++;             }         }         return (count>size/2)?true:false;     }