Finding the lexicographically smallest diameter in a binary tree
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. |
Python3
# Binary Tree Node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Utility function to find diameter def diameter(root, height, dia, heightv): # If root is None if root is None : height[ 0 ] = 0 return 0 # Left height and right height lh = [ 0 ] rh = [ 0 ] # Left tree diameter and right tree diameter ld = diameter(root.left, lh, dia, heightv) rd = diameter(root.right, rh, dia, heightv) # If left height is more than right tree height if lh[ 0 ] > rh[ 0 ]: # Add current root so lh + 1 height[ 0 ] = lh[ 0 ] + 1 # Change list heightv to leftheight heightv[:] = heightv[:lh[ 0 ]] # Insert current root in the path heightv.append(root) # If right height is more than left tree height elif rh[ 0 ] > lh[ 0 ]: # Add current root so rh + 1 height[ 0 ] = rh[ 0 ] + 1 # Change list heightv to rightheight heightv[:] = heightv[:rh[ 0 ]] # Insert current root in the path heightv.append(root) # Both height same compare lexicographically now else : # Add current root so rh + 1 height[ 0 ] = rh[ 0 ] + 1 # Lexicographical comparison between two lists if heightv[:lh[ 0 ]] < heightv[:rh[ 0 ]]: heightv[:] = heightv[:lh[ 0 ]] else : heightv[:] = heightv[:rh[ 0 ]] # Insert current root in the path heightv.append(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 > max (ld, rd): # Make dia equal to leftheight dia[:] = heightv[:] # Add current root into it dia.append(root) # Add right tree (right to root) nodes dia.extend( reversed (heightv[:rh[ 0 ]])) # If either left diameter containing the left subtree and # root or right diameter containing the right subtree and root is more than above lh+rh+1 else : # If diameter of left tree is greater our answer list i.e dia is equal to leftdia then if ld > rd: dia[:] = heightv[:lh[ 0 ]] # If both diameter same check lexicographically elif ld = = rd: if heightv[:lh[ 0 ]] < heightv[:rh[ 0 ]]: dia[:] = heightv[:lh[ 0 ]] else : dia[:] = heightv[:rh[ 0 ]] # If diameter of right tree is greater our answer list i.e dia is equal to rightdia then else : dia[:] = heightv[:rh[ 0 ]] return len (dia) # Driver code if __name__ = = "__main__" : # Creating the tree root = Node( 'a' ) root.left = Node( 'b' ) root.right = Node( 'c' ) root.left.left = Node( 'd' ) root.left.right = Node( 'e' ) root.right.left = Node( 'f' ) root.right.right = Node( 'g' ) height = [ 0 ] dia = [] heightv = [] print ( "Diameter is:" , diameter(root, height, dia, heightv)) # Printing the lexicographically smallest diameter print ( "Lexicographically smallest diameter:" ) for node in dia: print (node.data, end = " " ) |
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. |
Javascript
class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function to create a new node function newNode(data) { return new Node(data); } // Function to compare and return lexicographically smallest vector function compare(a, b) { for (let i = 0; i < a.length && i < b.length; 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 function diameter(root, height, dia, heightv) { if (root === null ) { height[0] = 0; return 0; } // Left height and right height respectively let lh = [0]; let rh = [0]; let leftdia = []; let rightdia = []; let leftheight = []; let rightheight = []; // Left tree diameter and right tree diameter let ld = diameter(root.left, lh, leftdia, leftheight); let 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.length = 0; heightv.push(...leftheight); heightv.push(root); } // If right height is more than left tree height else if (rh[0] > lh[0]) { height[0] = rh[0] + 1; heightv.length = 0; heightv.push(...rightheight); heightv.push(root); } // Both height same, compare lexicographically now else { height[0] = rh[0] + 1; heightv.length = 0; heightv.push(...compare(leftheight, rightheight)); heightv.push(root); } // If the 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.length = 0; dia.push(...leftheight); dia.push(root); for (let j = rightheight.length - 1; j >= 0; j--) { dia.push(rightheight[j]); } } // If either left diameter containing the left subtree and root or right diameter // containing the right subtree and root is more than above lh + rh + 1 else { if (ld > rd) { dia.length = 0; dia.push(...leftdia); } else if (ld === rd) { dia.length = 0; dia.push(...compare(leftdia, rightdia)); } else { dia.length = 0; dia.push(...rightdia); } } return dia.length; } // Main function function main() { const 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' ); const height = [0]; const dia = []; const heightv = []; console.log( "Diameter is: " + diameter(root, height, dia, heightv)); console.log( "Lexicographically smallest diameter:" ); for (let j = 0; j < dia.length; j++) { console.log(dia[j].data + " " ); } } // Run the main function main(); |
Output
Diameter is: 5 Lexicographically smallest diameter: d b a c f