Finding the lexicographically smallest diameter in a binary tree

0 0 7 minutes read

Given a binary tree where node values are lowercase alphabets, the task is to find the lexicographically smallest diameter. Diameter is the longest path between any two leaf nodes, hence, there can be multiple diameters in a Binary Tree. The task is to print the lexicographically smallest diameter among all possible diameters.
Examples:

Input:          
        a
      /   \
    b       c
  /  \     /  \
 d   e    f    g
Output: Diameter: 5
Lexicographically smallest diameter: d b a c f
Explanation:
Note that there are many other paths 
exist like {d, b, a, c, g}, 
{e, b, a, c, f} and {e, b, a, c, g} 
but {d, b, a, c, f} 
is lexicographically smallest
Input:          
        k
      /   \
    e       s
  /  \       
 g   f    
Output: Diameter: 4
Lexicographically smallest diameter: f e k s
Explanation:
Note that many other paths 
exist like {g, e, k, s} 
{s, k, e, g} and {s, k, e, f} 
but {f, e, k, s} is 
lexicographically smallest

Approach:
The approach is similar to finding diameter as discussed in the previous post. Now comes the part of
printing the longest path with the maximum diameter and lexicographically smallest.
Steps:

Custom compare function returns lexicographical smallest vector is made.
Six kinds of vector are been maintained which contains
the left subtree ( of a node) nodes in leftdiameter
the right subtree (of a node) nodes in rightdiameter
nodes occurring in the left height (of a node)
nodes occurring in the right height (of a node)
heightv vector contains the nodes occurring the path of max height
dia vector contains the nodes occurring the path of max height
Rest part is explained in the comments of code and it will be difficult to explain here in words

Below is the implementation of the above approach:

CPP

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Binary Tree Node
struct node {
    char data;
    node *left, *right;
};
 
// Utility function to create a new node
node* newNode(char data)
{
    node* c = new node;
    c->data = data;
    c->left = c->right = NULL;
    return c;
}
 
// Function to compare and return
// lexicographically smallest vector
vector<node*> compare(vector<node*> a, vector<node*> b)
{
    for (int i = 0; i < a.size() && i < b.size(); i++) {
        if (a[i]->data < b[i]->data) {
            return a;
        }
        if (a[i]->data > b[i]->data) {
            return b;
        }
    }
 
    return a;
}
 
// Function to find diameter
int diameter(node* root, int& height, vector<node*>& dia,
            vector<node*>& heightv)
{
    // If root is null
    if (!root) {
        height = 0;
        return 0;
    }
 
    // Left height and right height
    // respectively
    int lh = 0, rh = 0;
 
    // Left tree diameter and
    // right tree diameter
    int ld, rd;
 
    vector<node*> leftdia;
    vector<node*> rightdia;
    vector<node*> leftheight;
    vector<node*> rightheight;
 
    // Left subtree diameter
    ld = diameter(root->left, lh, leftdia, leftheight);
 
    // Right subtree diameter
    rd = diameter(root->right, rh, rightdia, rightheight);
 
    // If left height is more
    // than right tree height
    if (lh > rh) {
 
        // Add current root so lh + 1
        height = lh + 1;
 
        // Change vector heightv to leftheight
        heightv = leftheight;
 
        // Insert current root in the path
        heightv.push_back(root);
    }
 
    // If right height is
    // more than left tree height
    else if (rh > lh) {
 
        // Add current root so rh + 1
        height = rh + 1;
 
        // Change vector heightv to rightheight
        heightv = rightheight;
 
        // Insert current root in the path
        heightv.push_back(root);
    }
 
    // Both height same compare
    // lexicographically now
    else {
 
        // Add current root so rh + 1
        height = rh + 1;
 
        // Lexicographical comparison between two vectors
        heightv = compare(leftheight, rightheight);
 
        // Insert current root in the path
        heightv.push_back(root);
    }
 
    // If distance of one leaf node to another leaf
    // containing the root is more than the left
    // diameter and right diameter
    if (lh + rh + 1 > max(ld, rd)) {
 
        // Make dia equal to leftheight
        dia = leftheight;
 
        // Add current root into it
        dia.push_back(root);
 
        for (int j = rightheight.size() - 1; j >= 0; j--) {
            // Add right tree (right to root) nodes
            dia.push_back(rightheight[j]);
        }
    }
 
    // If either leftdiameter containing the left
    // subtree and root or rightdiameter containing
    // the right subtree and root is more than
    // above lh+rh+1
    else {
 
        // If diameter of left tree is
        // greater our answer vector i.e
        // dia is equal to leftdia then
        if (ld > rd) {
            dia = leftdia;
        }
 
        // If both diameter
        // same check lexicographically
        else if (ld == rd) {
            dia = compare(leftdia, rightdia);
        }
 
        // If diameter of right tree
        // is greater our answer vector
        // i.e dia is equal to rightdia then
        else {
            dia = rightdia;
        }
    }
 
    return dia.size();
}
 
// Driver code
int main()
{
    node* root = newNode('a');
    root->left = newNode('b');
    root->right = newNode('c');
    root->left->left = newNode('d');
    root->left->right = newNode('e');
    root->right->left = newNode('f');
    root->right->right = newNode('g');
 
    int height = 0;
    vector<node *> dia, heightv;
    cout << "Diameter is: " << diameter(root, height,
                                        dia, heightv)
        << endl;
 
    // Printing the lexicographically smallest diameter
    cout << "Lexicographically smallest diameter:" << endl;
    for (int j = 0; j < dia.size(); j++) {
        cout << dia[j]->data << " ";
    }
 
    return 0;
}

Java

// Java Program for the above approach
 
import java.util.*;
 
class Node {
    char data;
    Node left, right;
 
    Node(char val)
    {
        data = val;
        left = null;
        right = null;
    }
}
 
public class GFG {
    // Function to create a new node
    public static Node newNode(char data)
    {
        return new Node(data);
    }
 
    // Function to compare and return lexicographically
    // smallest vector
    public static List<Node> compare(List<Node> a,
                                     List<Node> b)
    {
        for (int i = 0; i < a.size() && i < b.size(); i++) {
            if (a.get(i).data < b.get(i).data) {
                return a;
            }
            if (a.get(i).data > b.get(i).data) {
                return b;
            }
        }
        return a;
    }
 
    // Function to find diameter of a binary tree
    public static int diameter(Node root, int[] height,
                               List<Node> dia,
                               List<Node> heightv)
    {
        if (root == null) {
            height[0] = 0;
            return 0;
        }
        // Left height and right height
        // respectively
        int[] lh = new int[1];
        int[] rh = new int[1];
 
        List<Node> leftdia = new ArrayList<>();
        List<Node> rightdia = new ArrayList<>();
        List<Node> leftheight = new ArrayList<>();
        List<Node> rightheight = new ArrayList<>();
 
        // Left tree diameter and
        // right tree diameter
        int ld
            = diameter(root.left, lh, leftdia, leftheight);
        int rd = diameter(root.right, rh, rightdia,
                          rightheight);
        // If left height is more
        // than right tree height
        if (lh[0] > rh[0]) {
            height[0] = lh[0] + 1;
            heightv.clear();
            heightv.addAll(leftheight);
            heightv.add(root);
        }
        // If right height is
        // more than left tree height
        else if (rh[0] > lh[0]) {
            height[0] = rh[0] + 1;
            heightv.clear();
            heightv.addAll(rightheight);
            heightv.add(root);
        }
        // Both height same compare
        // lexicographically now
        else {
            height[0] = rh[0] + 1;
            heightv.clear();
            heightv.addAll(
                compare(leftheight, rightheight));
            heightv.add(root);
        }
 
        // If distance of one leaf node to another leaf
        // containing the root is more than the left
        // diameter and right diameter
        if (lh[0] + rh[0] + 1 > Math.max(ld, rd)) {
            dia.clear();
            dia.addAll(leftheight);
            dia.add(root);
            for (int j = rightheight.size() - 1; j >= 0;
                 j--) {
                dia.add(rightheight.get(j));
            }
        }
        // If either leftdiameter containing the left
        // subtree and root or rightdiameter containing
        // the right subtree and root is more than
        // above lh+rh+1
        else {
            if (ld > rd) {
                dia.clear();
                dia.addAll(leftdia);
            }
            else if (ld == rd) {
                dia.clear();
                dia.addAll(compare(leftdia, rightdia));
            }
            else {
                dia.clear();
                dia.addAll(rightdia);
            }
        }
 
        return dia.size();
    }
 
    public static void main(String[] args)
    {
        Node root = newNode('a');
        root.left = newNode('b');
        root.right = newNode('c');
        root.left.left = newNode('d');
        root.left.right = newNode('e');
        root.right.left = newNode('f');
        root.right.right = newNode('g');
 
        int[] height = new int[1];
        List<Node> dia = new ArrayList<>();
        List<Node> heightv = new ArrayList<>();
        System.out.println(
            "Diameter is: "
            + diameter(root, height, dia, heightv));
 
        System.out.println(
            "Lexicographically smallest diameter:");
        for (int j = 0; j < dia.size(); j++) {
            System.out.print(dia.get(j).data + " ");
        }
    }
}
 
// This code is contributed by Taranpreet Singh.

C#

using System;
using System.Collections.Generic;
 
public class Node {
    public char data;
    public Node left, right;
 
    public Node(char val)
    {
        data = val;
        left = null;
        right = null;
    }
}
 
public class GFG {
    // Function to create a new node
    public static Node newNode(char data)
    {
        return new Node(data);
    }
 
    // Function to compare and return lexicographically
    // smallest vector
    public static List<Node> compare(List<Node> a,
                                     List<Node> b)
    {
        for (int i = 0; i < a.Count && i < b.Count; i++) {
            if (a[i].data < b[i].data) {
                return a;
            }
            if (a[i].data > b[i].data) {
                return b;
            }
        }
        return a;
    }
 
    // Function to find diameter of a binary tree
    public static int diameter(Node root, int[] height,
                               List<Node> dia,
                               List<Node> heightv)
    {
        if (root == null) {
            height[0] = 0;
            return 0;
        }
 
        int[] lh = new int[1];
        int[] rh = new int[1];
 
        List<Node> leftdia = new List<Node>();
        List<Node> rightdia = new List<Node>();
        List<Node> leftheight = new List<Node>();
        List<Node> rightheight = new List<Node>();
 
        int ld
            = diameter(root.left, lh, leftdia, leftheight);
        int rd = diameter(root.right, rh, rightdia,
                          rightheight);
 
        if (lh[0] > rh[0]) {
            height[0] = lh[0] + 1;
            heightv.Clear();
            heightv.AddRange(leftheight);
            heightv.Add(root);
        }
        else if (rh[0] > lh[0]) {
            height[0] = rh[0] + 1;
            heightv.Clear();
            heightv.AddRange(rightheight);
            heightv.Add(root);
        }
        else {
            height[0] = rh[0] + 1;
            heightv.Clear();
            heightv.AddRange(
                compare(leftheight, rightheight));
            heightv.Add(root);
        }
 
        if (lh[0] + rh[0] + 1 > Math.Max(ld, rd)) {
            dia.Clear();
            dia.AddRange(leftheight);
            dia.Add(root);
            for (int j = rightheight.Count - 1; j >= 0;
                 j--) {
                dia.Add(rightheight[j]);
            }
        }
        else {
            if (ld > rd) {
                dia.Clear();
                dia.AddRange(leftdia);
            }
            else if (ld == rd) {
                dia.Clear();
                dia.AddRange(compare(leftdia, rightdia));
            }
            else {
                dia.Clear();
                dia.AddRange(rightdia);
            }
        }
 
        return dia.Count;
    }
 
    public static void Main(string[] args)
    {
        Node root = newNode('a');
        root.left = newNode('b');
        root.right = newNode('c');
        root.left.left = newNode('d');
        root.left.right = newNode('e');
        root.right.left = newNode('f');
        root.right.right = newNode('g');
 
        int[] height = new int[1];
        List<Node> dia = new List<Node>();
        List<Node> heightv = new List<Node>();
 
        Console.WriteLine(
            "Diameter is: "
            + diameter(root, height, dia, heightv));
        Console.WriteLine(
            "Lexicographically smallest diameter:");
 
        for (int j = 0; j < dia.Count; j++) {
            Console.Write(dia[j].data + " ");
        }
    }
}
 
// This code is contributed by Taranpreet Singh.

Output

Diameter is: 5
Lexicographically smallest diameter:
d b a c f

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!