Print the elements of given two Binary Trees in sorted order
Given two binary trees, the task is to print the elements of both the binary trees in non-decreasing order.
Examples:
Input: Trees in the image below
Output: 1 2 3 4 5 6
Explanation: The nodes in the 1st and 2nd binary tree are {3, 1, 5} and {4, 2, 6} respectively. Upon merging and sorting the two arrays, the required array becomes {1, 2, 3, 4, 5, 6} which is the required answer.Input: Trees in the image below
Output: 0 1 2 3 5 8 10
Approach: The given problem can be solved using the following steps:
- Create a map to store each element present in both trees along with their frequencies.
- Traverse the first tree and insert each element with its frequency in the map.
- Similarly, traverse the first tree and insert each element with its frequency in the map.
- Traverse the map and print all elements, their frequency times.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Structure of a binary tree node class node { public : int data; node* left; node* right; }; // Helper function that allocates // a new node with the given data node* newNode( int data) { node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; return (Node); } // Map to store all elements // from given two trees map< int , int > m; // Recursive function to perform // inorder traversal on tree void traverse(node* root) { // Base Case if (root == NULL) return ; else { // Update map m[root->data]++; } // Recursive call for left subtree traverse(root->left); // Recursive call for right subtree traverse(root->right); } // Function to print all the elements of // two given binary trees in sorted order void printAllElements(node* root1, node* root2) { // Traverse the 1st tree traverse(root1); // Traverse the 2nd tree traverse(root2); // Traverse the map for ( auto it : m) { // Print current element // its frequency times for ( int i = 0; i < it.second; i++) { cout << it.first << " " ; } } } // Driver code int main() { node* root1 = newNode(8); root1->left = newNode(2); root1->right = newNode(10); root1->left->left = newNode(1); node* root2 = newNode(5); root2->left = newNode(3); root2->right = newNode(0); printAllElements(root1, root2); return 0; } |
Java
// Java program of the above approach import java.io.*; import java.lang.*; import java.util.*; // Structure of a binary tree node public class GFG{ public static class Node { int data; Node left, right; Node( int data) { left=right= null ; this .data=data; } } // Map to store all elements // from given two trees public static Map<Integer, Integer> m = new HashMap<>(); // Recursive function to perform // inorder traversal on tree public static void traverse(Node root) { // Base Case if (root == null ) return ; else { // Update map if (m.containsKey(root.data)) m.put(root.data,m.get(root.data)+ 1 ); else m.put(root.data, 1 ); } // Recursive call for left subtree traverse(root.left); // Recursive call for right subtree traverse(root.right); } // Function to print all the elements of // two given binary trees in sorted order public static void printAllElements(Node root1, Node root2) { // Traverse the 1st tree traverse(root1); // Traverse the 2nd tree traverse(root2); // Traverse the map for (Map.Entry<Integer,Integer> it : m.entrySet()) { // Print current element // its frequency times for ( int i = 0 ; i < it.getValue(); i++) { System.out.print(it.getKey()+ " " ); } } } // Driver code public static void main(String[] args) { Node root1 = new Node( 8 ); root1.left = new Node( 2 ); root1.right = new Node( 10 ); root1.left.left = new Node( 1 ); Node root2 = new Node( 5 ); root2.left = new Node( 3 ); root2.right = new Node( 0 ); printAllElements(root1, root2); } } // This code is contributed by Pushpesh raj. |
Python3
# Python code for the above approach # Structure of a binary tree node class node: def __init__( self , d): self .data = d self .left = None self .right = None # Map to store all elements # from given two trees m = {} # Recursive function to perform # inorder traversal on tree def traverse(root): # Base Case if (root = = None ): return else : # Update map if (root.data in m): m[root.data] + = 1 else : m[root.data] = 1 # Recursive call for left subtree traverse(root.left) # Recursive call for right subtree traverse(root.right) # Function to print all the elements of # two given binary trees in sorted order def printAllElements(root1, root2): # Traverse the 1st tree traverse(root1) # Traverse the 2nd tree traverse(root2) v = [] # Traverse the map for key in m: # Print current element # its frequency times for i in range (m[key]): v.append(key) v.sort() for i in range ( len (v)): print (v[i], end = " " ) # Driver code root1 = node( 8 ) root1.left = node( 2 ) root1.right = node( 10 ) root1.left.left = node( 1 ) root2 = node( 5 ) root2.left = node( 3 ) root2.right = node( 0 ) printAllElements(root1, root2) # This code is contributed by Saurabh Jaiswal |
C#
// C# program of the above approach using System; using System.Collections; using System.Collections.Generic; public class GFG { // Structure of a binary tree node public class Node { public int data; public Node left, right; public Node( int data) { left = right = null ; this .data = data; } } // Dictionary to store all elements from given two trees static Dictionary< int , int > m = new Dictionary< int , int >(); // Recursive function to perform inorder traversal on // tree public static void traverse(Node root) { // Base Case if (root == null ) return ; else { // Update map if (m.ContainsKey(root.data)) m[root.data] += 1; else m.Add(root.data, 1); } // Recursive call for left subtree traverse(root.left); // Recursive call for right subtree traverse(root.right); } // Function to print all the elements of two given // binary trees in sorted order public static void printAllElements(Node root1, Node root2) { // Traverse the 1st tree traverse(root1); // Traverse the 2nd tree traverse(root2); ArrayList v = new ArrayList(); // Traverse the map. foreach (KeyValuePair< int , int > it in m) { for ( int i = 0; i < it.Value; i++) { v.Add(it.Key); } } v.Sort(); foreach ( var i in v) { Console.Write(i + " " ); } } static public void Main() { // Code Node root1 = new Node(8); root1.left = new Node(2); root1.right = new Node(10); root1.left.left = new Node(1); Node root2 = new Node(5); root2.left = new Node(3); root2.right = new Node(0); printAllElements(root1, root2); } } // This code is contributed by lokesh (lokeshmvs21). |
Javascript
<script> // JavaScript code for the above approach // Structure of a binary tree node class node { constructor(d) { this .data = d; this .left = null ; this .right = null ; } }; // Map to store all elements // from given two trees let m = new Map(); // Recursive function to perform // inorder traversal on tree function traverse(root) { // Base Case if (root == null ) return ; else { // Update map if (m.has(root.data)) { m.set(root.data, m.get(root.data) + 1); } else { m.set(root.data, 1) } } // Recursive call for left subtree traverse(root.left); // Recursive call for right subtree traverse(root.right); } // Function to print all the elements of // two given binary trees in sorted order function printAllElements(root1, root2) { // Traverse the 1st tree traverse(root1); // Traverse the 2nd tree traverse(root2); let v = [] // Traverse the map for (let [key, val] of m) { // Print current element // its frequency times for (let i = 0; i < val; i++) { v.push(key); } } v.sort( function (a, b) { return a - b }) for (let i = 0; i < v.length; i++) { document.write(v[i] + " " ) } } // Driver code let root1 = new node(8); root1.left = new node(2); root1.right = new node(10); root1.left.left = new node(1); let root2 = new node(5); root2.left = new node(3); root2.right = new node(0); printAllElements(root1, root2); // This code is contributed by Potta Lokesh </script> |
0 1 2 3 5 8 10
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Method 2 ( merge sort algorithm)
The way to solve this problem is to use a modified version of the merge step of the merge sort algorithm.
Algorithm
1. Initialize an empty dictionary called `freq_map` to store the frequency of each node's value.
2. Traverse the first binary tree in inorder and update the frequency map with each node's value.
3. Traverse the second binary tree in inorder and update the frequency map with each node's value.
4. Initialize an empty list called `merged` to hold the merged values.
5. Iterate through the keys of the frequency map in sorted order.
6. For each key, append the key to the `merged` list the number of times it appears in the frequency map.
7. Return the `merged` list.
C++
//C++ code for the above approach #include <iostream> #include <vector> #include <map> // Define a binary tree node class with a value, left child, // and right child struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode( int val) { this ->val = val; this ->left = nullptr; this ->right = nullptr; } }; // Forward declarations void inorderTraversal(TreeNode* root, std::map< int , int >& freqMap); std::vector< int > mergeTrees(TreeNode* root1, TreeNode* root2); // Define a function to merge two binary trees into a // sorted list of their values std::vector< int > mergeTrees(TreeNode* root1, TreeNode* root2) { // Create a map to store the frequency of each // node's value (automatically sorted by key) std::map< int , int > freqMap; // Traverse the first tree in inorder and update the // frequency map inorderTraversal(root1, freqMap); // Traverse the second tree in inorder and update // the frequency map inorderTraversal(root2, freqMap); // Create an empty vector to hold the merged values std::vector< int > merged; // Iterate through the keys of the frequency map // (sorted order) for ( const auto & entry : freqMap) { // Append the value to the merged vector the // number of times it appears in the frequency // map int key = entry.first; int freq = entry.second; for ( int i = 0; i < freq; i++) { merged.push_back(key); } } // Return the merged vector return merged; } // Define a function to traverse a binary tree in // inorder and update the frequency map void inorderTraversal(TreeNode* root, std::map< int , int >& freqMap) { // If the root is null, return if (root == nullptr) { return ; } // Traverse the left subtree inorderTraversal(root->left, freqMap); // Update the frequency of the current node's value // in the frequency map freqMap[root->val]++; // Traverse the right subtree inorderTraversal(root->right, freqMap); } // Main function to test the code int main() { // Example usage: // Create two binary trees TreeNode* root1 = new TreeNode(8); root1->left = new TreeNode(2); root1->right = new TreeNode(10); root1->left->left = new TreeNode(1); TreeNode* root2 = new TreeNode(5); root2->left = new TreeNode(3); root2->right = new TreeNode(0); // Merge the trees and store the result std::vector< int > merged = mergeTrees(root1, root2); // Print the result in the specified format std::cout << "[" ; for ( size_t i = 0; i < merged.size(); i++) { std::cout << merged[i]; if (i < merged.size() - 1) { std::cout << ", " ; } } std::cout << "]" << std::endl; // Output: [0, 1, 2, 3, 5, 8, 10] // Don't forget to free the dynamically allocated memory // ReleaseMemory(root1); // ReleaseMemory(root2); return 0; } |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.TreeMap; // Define a binary tree node class with a value, left child, // and right child class TreeNode { int val; TreeNode left; TreeNode right; TreeNode( int val) { this .val = val; this .left = null ; this .right = null ; } } public class GFG { // Define a function to merge two binary trees into a // sorted list of their values public static List<Integer> mergeTrees(TreeNode root1, TreeNode root2) { // Create a TreeMap to store the frequency of each // node's value (automatically sorted by key) Map<Integer, Integer> freqMap = new TreeMap<>(); // Traverse the first tree in inorder and update the // frequency map inorderTraversal(root1, freqMap); // Traverse the second tree in inorder and update // the frequency map inorderTraversal(root2, freqMap); // Create an empty list to hold the merged values List<Integer> merged = new ArrayList<>(); // Iterate through the keys of the frequency map // (sorted order) for ( int key : freqMap.keySet()) { // Append the value to the merged list the // number of times it appears in the frequency // map int freq = freqMap.get(key); for ( int i = 0 ; i < freq; i++) { merged.add(key); } } // Return the merged list return merged; } // Define a function to traverse a binary tree in // inorder and update the frequency map private static void inorderTraversal(TreeNode root, Map<Integer, Integer> freqMap) { // If the root is null, return if (root == null ) { return ; } // Traverse the left subtree inorderTraversal(root.left, freqMap); // Update the frequency of the current node's value // in the frequency map freqMap.put(root.val, freqMap.getOrDefault(root.val, 0 ) + 1 ); // Traverse the right subtree inorderTraversal(root.right, freqMap); } // Main function to test the code public static void main(String[] args) { // Example usage: // Create two binary trees TreeNode root1 = new TreeNode( 8 ); root1.left = new TreeNode( 2 ); root1.right = new TreeNode( 10 ); root1.left.left = new TreeNode( 1 ); TreeNode root2 = new TreeNode( 5 ); root2.left = new TreeNode( 3 ); root2.right = new TreeNode( 0 ); // Merge the trees and print the result List<Integer> merged = mergeTrees(root1, root2); System.out.println( merged); // Output: [0, 1, 2, 3, 5, 8, 10] } } |
Python
# Define a binary tree node class with a value, left child, and right child class TreeNode: def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right # Define a function to merge two binary trees into a sorted list of their values def merge_trees(root1, root2): # Create a dictionary to store the frequency of each node's value freq_map = {} # Traverse the first tree in inorder and update the frequency map inorder_traversal(root1, freq_map) # Traverse the second tree in inorder and update the frequency map inorder_traversal(root2, freq_map) # Create an empty list to hold the merged values merged = [] # Iterate through the keys of the frequency map in sorted order for key in sorted (freq_map.keys()): # Append the value to the merged list the number of times it appears in the frequency map merged.extend([key] * freq_map[key]) # Return the merged list return merged # Define a function to traverse a binary tree in inorder and update the frequency map def inorder_traversal(root, freq_map): # If the root is None, return if root is None : return # Traverse the left subtree inorder_traversal(root.left, freq_map) # Update the frequency of the current node's value in the frequency map freq_map[root.val] = freq_map.get(root.val, 0 ) + 1 # Traverse the right subtree inorder_traversal(root.right, freq_map) # Example usage: # Create two binary trees root1 = TreeNode( 8 ) root1.left = TreeNode( 2 ) root1.right = TreeNode( 10 ) root1.left.left = TreeNode( 1 ) root2 = TreeNode( 5 ) root2.left = TreeNode( 3 ) root2.right = TreeNode( 0 ) # Merge the trees and print the result merged = merge_trees(root1, root2) print (merged) # Output: [1, 2, 3, 4, 5, 6] |
C#
using System; using System.Collections.Generic; using System.Linq; using System.Collections; // Define a binary tree node class with a value, left child, // and right child public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode( int val) { this .val = val; this .left = null ; this .right = null ; } } public class GFG { // Define a function to merge two binary trees into a // sorted list of their values public static List< int > MergeTrees(TreeNode root1, TreeNode root2) { // Create a TreeMap to store the frequency of each // node's value (automatically sorted by key) SortedDictionary< int , int > freqMap = new SortedDictionary< int , int >(); // Traverse the first tree in inorder and update the // frequency map InorderTraversal(root1, freqMap); // Traverse the second tree in inorder and update // the frequency map InorderTraversal(root2, freqMap); // Create an empty list to hold the merged values List< int > merged = new List< int >(); // Iterate through the keys of the frequency map // (sorted order) foreach ( int key in freqMap.Keys) { // Append the value to the merged list the // number of times it appears in the frequency // map int freq = freqMap[key]; for ( int i = 0; i < freq; i++) { merged.Add(key); } } // Return the merged list return merged; } // Define a function to traverse a binary tree in // inorder and update the frequency map private static void InorderTraversal(TreeNode root, SortedDictionary< int , int > freqMap) { // If the root is null, return if (root == null ) { return ; } // Traverse the left subtree InorderTraversal(root.left, freqMap); // Update the frequency of the current node's value // in the frequency map if (freqMap.ContainsKey(root.val)) { freqMap[root.val]++; } else { freqMap[root.val] = 1; } // Traverse the right subtree InorderTraversal(root.right, freqMap); } // Main function to test the code public static void Main( string [] args) { // Example usage: // Create two binary trees TreeNode root1 = new TreeNode(8); root1.left = new TreeNode(2); root1.right = new TreeNode(10); root1.left.left = new TreeNode(1); TreeNode root2 = new TreeNode(5); root2.left = new TreeNode(3); root2.right = new TreeNode(0); // Merge the trees and print the result List< int > merged = MergeTrees(root1, root2); Console.WriteLine( "{" + string .Join( ", " , merged)+ "}" ); // Output: 0, 1, 2, 3, 5, 8, 10 } } // This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
// Define a binary tree node class with a value, left child, // and right child class TreeNode { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } // Forward declarations function inorderTraversal(root, freqMap) { if (root === null ) { return ; } inorderTraversal(root.left, freqMap); freqMap[root.val] = (freqMap[root.val] || 0) + 1; inorderTraversal(root.right, freqMap); } function mergeTrees(root1, root2) { // Create a map to store the frequency of each // node's value (automatically sorted by key) const freqMap = {}; // Traverse the first tree in inorder and update the // frequency map inorderTraversal(root1, freqMap); // Traverse the second tree in inorder and update // the frequency map inorderTraversal(root2, freqMap); // Create an empty array to hold the merged values const merged = []; // Iterate through the keys of the frequency map // (sorted order) Object.keys(freqMap).forEach((key) => { const freq = freqMap[key]; for (let i = 0; i < freq; i++) { merged.push(parseInt(key)); } }); // Return the merged array return merged; } // Main function to test the code function main() { // Example usage: // Create two binary trees const root1 = new TreeNode(8); root1.left = new TreeNode(2); root1.right = new TreeNode(10); root1.left.left = new TreeNode(1); const root2 = new TreeNode(5); root2.left = new TreeNode(3); root2.right = new TreeNode(0); // Merge the trees and store the result const merged = mergeTrees(root1, root2); // Print the result in the specified format console.log( "[" + merged.join( ", " ) + "]" ); // Output: [0, 1, 2, 3, 5, 8, 10] // Don't forget to free the dynamically allocated memory // (JavaScript handles memory management automatically) } // Call the main function main(); |
[0, 1, 2, 3, 5, 8, 10]
Time complexity: O(nlogn), where n is the total number of elements in both trees.
Space complexity: O(n), where n is the total number of nodes in the input binary trees.