Given a Binary Tree with positive values at each node, the task is to print the maximum number that can be formed by arranging nodes at each level.
Examples:
Input: 4
/ \
2 59
/ \ / \
1 3 2 6
Output:
Maximum number at 0'th level is 4
Maximum number at 1'st level is 592
Maximum number at 2'nd level is 6321
Input: 1
/ \
2 3
/ \ \
4 5 8
/ \
6 79
Output:
Explanation :
The maximum number at the 0'th level is 1
The maximum number at 1'st level is 32
The maximum number at 2'nd level is 854
The maximum number at 3'rd level is 796
Approach:
- Traverse all nodes at each level one by one using Level Order Traversal.
- Store their values in a vector of strings.
- Sort the vector using Comparison method to generate greatest number possible.
- Display the number and repeat the procedure for all levels.
Below code is the implementation of the above approach:
C++
// C++ program to find maximum number// possible from nodes at each level.#include <bits/stdc++.h>using namespace std;/* A binary tree node representation */struct Node { int data; struct Node *left, *right;};int myCompare(string X, string Y){ // first append Y at the end of X string XY = X.append(Y); // then append X at the end of Y string YX = Y.append(X); // Now see which of the two formed numbers is greater return XY.compare(YX) > 0 ? 1 : 0;}// Function to print the largest value// from the vector of stringsvoid printLargest(vector<string> arr){ // Sort the numbers using comparison function // myCompare() to compare two strings. // Refer http:// www.cplusplus.com/reference/algorithm/sort/ sort(arr.begin(), arr.end(), myCompare); for (int i = 0; i < arr.size(); i++) cout << arr[i]; cout << "\n";}// Function to return the maximum number// possible from nodes at each level// using level order traversalint maxLevelNumber(struct Node* root){ // Base case if (root == NULL) return 0; // Initialize result int result = root->data; // Level Order Traversal queue<Node*> q; q.push(root); while (!q.empty()) { // Get the size of the queue for the level int count = q.size(); vector<string> v; // Iterate over all the nodes while (count--) { // Dequeue nodes from queue Node* temp = q.front(); q.pop(); // push that node to vector v.push_back(to_string(temp->data)); // Push left and right nodes to queue // if present if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); } // Print the maximum number at that level printLargest(v); } return result;}/* Helper function that allocates a new node with thegiven data and NULL left and right pointers. */struct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);}// Driver codeint main(){ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->right = newNode(8); root->right->right->left = newNode(6); root->right->right->right = newNode(7); /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ maxLevelNumber(root); return 0;} |
Java
// Java program to find maximum number // possible from nodes at each levelimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Node structurestatic class node{ int data; node left = null; node right = null;}// Creates and initialize a new nodestatic node newNode(int ch){ // Allocating memory to a new node node n = new node(); n.data = ch; n.left = null; n.right = null; return n;}// Function to print the largest value// from the vector of stringsstatic void printLargest(ArrayList<String> arr){ // Sort the numbers using comparison function // myCompare() to compare two strings. // Refer http:// www.cplusplus.com/reference/algorithm/sort/ Collections.sort(arr,new Comparator<>() { public int compare(String X, String Y) { // First append Y at the end of X String XY = X + Y; // Then append X at the end of Y String YX = Y + X; // Now see which of the two // formed numbers is greater return XY.compareTo(YX) > 0 ? -1 : 1; } }); for(int i = 0; i < arr.size(); i++) System.out.print(arr.get(i)); System.out.println();}// Function to return the maximum number// possible from nodes at each level// using level order traversalstatic int maxLevelNumber(node root){ // Base case if (root == null) return 0; // Initialize result int result = root.data; // Level Order Traversal Queue<node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { // Get the size of the queue // for the level int count = q.size(); ArrayList<String> v = new ArrayList<>(); // Iterate over all the nodes while (count-->0) { // Dequeue nodes from queue node temp = q.peek(); q.poll(); // push that node to vector v.add(Integer.toString(temp.data)); // Push left and right nodes to queue // if present if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } // Print the maximum number at that level printLargest(v); } return result;}// Driver codepublic static void main (String[] args){ node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(8); root.right.right.left = newNode(6); root.right.right.right = newNode(7); /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ maxLevelNumber(root);}}// This code is contributed by offbeat |
Python3
# Python3 program to find maximum number# possible from nodes at each level.import queuefrom functools import cmp_to_key# A binary tree node representationclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to compare two stringsdef myCompare(X, Y): # first append Y at the end of X XY = X + Y # then append X at the end of Y YX = Y + X # Now see which of the two formed numbers is greater if XY < YX: return 0 else: return 1# Function to print the largest value# from the list of stringsdef printLargest(arr): # Sort the numbers using comparison function # myCompare() to compare two strings arr.sort(key=cmp_to_key(myCompare)) for i in range(len(arr)-1, -1, -1): print(arr[i], end='') print()# Function to return the maximum number# possible from nodes at each level# using level order traversaldef maxLevelNumber(root): # Base case if root is None: return 0 # Initialize result result = root.data # Level Order Traversal q = queue.Queue() q.put(root) while not q.empty(): # Get the size of the queue for the level count = q.qsize() v = [] # Iterate over all the nodes while count > 0: # Dequeue nodes from queue temp = q.get() # append that node to list v.append(str(temp.data)) # Push left and right nodes to queue # if present if temp.left is not None: q.put(temp.left) if temp.right is not None: q.put(temp.right) count -= 1 # Print the maximum number at that level printLargest(v) return result# Driver codeif __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(8) root.right.right.left = Node(6) root.right.right.right = Node(7) # Constructed Binary tree is: # 1 # / \ # 2 3 # / \ \ # 4 5 8 # / \ # 6 7 maxLevelNumber(root)# This code is contributed by Potta Lokesh |
C#
using System.Collections.Generic;using System;class Node{ public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}class Tree{ static int myCompare(string X, string Y) { string XY = X + Y; string YX = Y + X; return XY.CompareTo(YX); } static void printLargest(List<string> arr) { arr.Sort((a, b) => myCompare(b, a)); Console.WriteLine(string.Join("", arr)); } static int maxLevelNumber(Node root) { if (root == null) return 0; int result = root.data; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { int count = q.Count; List<string> v = new List<string>(); while (count > 0) { Node temp = q.Dequeue(); v.Add(temp.data.ToString()); if (temp.left != null) q.Enqueue(temp.left); if (temp.right != null) q.Enqueue(temp.right); count--; } printLargest(v); } return result; } static void Main(string[] args) { Node 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.right = new Node(8); root.right.right.left = new Node(6); root.right.right.right = new Node(7); // Constructed Binary tree is:// 1// / \// 2 3// / \ \// 4 5 8// / \// 6 7 maxLevelNumber(root); }}// This code is provided by mukul ojha |
Javascript
// JavaScript program to find the maximum number possible from nodes at each level.// Node structure for the binary treeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}// Comparison function to compare two stringsfunction myCompare(X, Y) { // First append Y at the end of X let XY = X + Y; // Then append X at the end of Y let YX = Y + X; // Now see which of the two formed numbers is greater return XY.localeCompare(YX) > 0 ? -1 : 1; // Corrected: Change < to >}// Function to print the largest value from the array of stringsfunction printLargest(arr) { // Sort the numbers using the comparison function myCompare arr.sort(myCompare); // Print the sorted numbers console.log(arr.join(''));}// Function to return the maximum number possible from nodes at each level using level order traversalfunction maxLevelNumber(root) { // Base case if (!root) return 0; // Initialize result let result = root.data; // Level Order Traversal using a queue let q = []; q.push(root); while (q.length > 0) { // Get the size of the queue for the level let count = q.length; let v = []; // Iterate over all the nodes at the current level while (count--) { // Dequeue nodes from the queue let temp = q.shift(); // Push that node's data to the array v.push(String(temp.data)); // Push left and right nodes to the queue if present if (temp.left !== null) q.push(temp.left); if (temp.right !== null) q.push(temp.right); } // Print the maximum number at that level printLargest(v); } return result;}// Helper function that allocates a new node with the given data and NULL left and right pointersfunction newNode(data) { let node = new Node(data); return node;}// Driver codefunction main() { let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.right = newNode(8); root.right.right.left = newNode(6); root.right.right.right = newNode(7); /* Constructed Binary tree is: 1 / \ 2 3 / \ \ 4 5 8 / \ 6 7 */ maxLevelNumber(root);}// Call the main functionmain();// This code is contributed by Dwaipayan Bandyopadhyay |
Output
1 32 854 76
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
