Construct a Maximum Binary Tree from two given Binary Trees

0 0 7 minutes read

Given two Binary Trees, the task is to create a Maximum Binary Tree from the two given binary trees and print the Inorder Traversal of that tree.

What is the maximum Binary Tree?

The maximum binary is constructed in the following manner:
In the case of both the Binary Trees having two corresponding nodes, the maximum of the two values is considered as the node value of the Maximum Binary Tree.
If any of the two nodes is NULL and if the other node is not null, insert that value on that node of the Maximum Binary Tree.

Example:

Input:
Tree 1                Tree 2
   3                    5 
  / \                  / \
 2   6                1   8 
/                      \   \ 
20                      2   8 
Output: 20 2 2 5 8 8
Explanation:
          5
         / \
        2   8
       / \   \
      20   2   8

To construct the required Binary Tree,
Root Node value: Max(3, 5) = 5
Root->left value: Max(2, 1) = 2
Root->right value: Max(6, 8) = 8
Root->left->left value: 20
Root->left->right value: 2
Root->right->right value: 8

Input:
       Tree 1            Tree 2 
         9                 5
        / \               / \
       2   6             1   8
      / \                 \   \
     20  3                 2   8
Output:  20 2 3 9 8 8
Explanation:
          9
         / \
        2   8
       / \   \
      20  3   8

Approach:
Follow the steps given below to solve the problem:

Traverse both the trees using preorder traversal.
If both the nodes are NULL, return. Otherwise, check for the following conditions:
- If both the nodes are not NULL then store the maximum between them as the node value of the Maximum Binary Tree.
- If only one of the node is NULL store the value of the non-NULL node as the node value of the Maximum Binary Tree.
Recursively traverse the left subtrees.
Recursively traverse the right subtrees
Finally, return the root of the Maximum Binary Tree.

Below is the implementation of the above approach:

C++

// C++ program to find the Maximum 
// Binary Tree from two Binary Trees 
#include<bits/stdc++.h>
using namespace std;
  
// A binary tree node has data, 
// pointer to left child 
// and a pointer to right child 
class Node{
     
public:
int data; 
Node *left, *right; 
   
Node(int data, Node *left, 
               Node *right) 
{ 
    this->data = data; 
    this->left = left; 
    this->right = right; 
}
};
  
// Helper method that allocates 
// a new node with the given data 
// and NULL left and right pointers. 
Node* newNode(int data) 
{ 
    Node *tmp = new Node(data, NULL, NULL); 
    return tmp;
} 
  
// Given a binary tree, print 
// its nodes in inorder
void inorder(Node *node) 
{ 
    if (node == NULL) 
        return; 
  
    // First recur on left child 
    inorder(node->left); 
  
    // Then print the data of node 
    cout << node->data << " "; 
  
    // Now recur on right child 
    inorder(node->right); 
} 
  
// Method to find the maximum 
// binary tree from two binary trees
Node* MaximumBinaryTree(Node *t1, Node *t2) 
{ 
    if (t1 == NULL) 
        return t2; 
    if (t2 == NULL) 
        return t1; 
  
    t1->data = max(t1->data, t2->data); 
    t1->left = MaximumBinaryTree(t1->left, 
                                 t2->left); 
    t1->right = MaximumBinaryTree(t1->right, 
                                  t2->right); 
    return t1; 
} 
  
// Driver Code 
int main()
{
     
    /* First Binary Tree 
             3 
            / \ 
           2   6 
         / 
        20 
    */
  
    Node *root1 = newNode(3); 
    root1->left = newNode(2); 
    root1->right = newNode(6); 
    root1->left->left = newNode(20); 
  
    /* Second Binary Tree 
            5 
           / \ 
          1   8 
           \   \ 
            2   8 
            */
    Node *root2 = newNode(5); 
    root2->left = newNode(1); 
    root2->right = newNode(8); 
    root2->left->right = newNode(2); 
    root2->right->right = newNode(8); 
  
    Node *root3 = MaximumBinaryTree(root1, root2); 
    inorder(root3); 
} 
 
// This code is contributed by pratham76

Java

// Java program to find the Maximum
// Binary Tree from two Binary Trees
 
/* A binary tree node has data,
 pointer to left child
and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    public Node(int data, Node left,
                Node right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }
 
    /* Helper method that allocates
       a new node with the given data 
       and NULL left and right pointers. */
    static Node newNode(int data)
    {
        return new Node(data, null, null);
    }
 
    /* Given a binary tree, print 
       its nodes in inorder*/
    static void inorder(Node node)
    {
        if (node == null)
            return;
 
        /* first recur on left child */
        inorder(node.left);
 
        /* then print the data of node */
        System.out.printf("%d ", node.data);
 
        /* now recur on right child */
        inorder(node.right);
    }
 
    /* Method to find the maximum 
       binary tree from
       two binary trees*/
    static Node MaximumBinaryTree(Node t1, Node t2)
    {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.data = Math.max(t1.data, t2.data);
        t1.left = MaximumBinaryTree(t1.left,
                                    t2.left);
        t1.right = MaximumBinaryTree(t1.right,
                                     t2.right);
        return t1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        /* First Binary Tree
                 3
                / \
               2   6
              /
             20
        */
 
        Node root1 = newNode(3);
        root1.left = newNode(2);
        root1.right = newNode(6);
        root1.left.left = newNode(20);
 
        /* Second Binary Tree
                 5
                / \
                1  8
                \   \
                  2   8
                  */
        Node root2 = newNode(5);
        root2.left = newNode(1);
        root2.right = newNode(8);
        root2.left.right = newNode(2);
        root2.right.right = newNode(8);
 
        Node root3
            = MaximumBinaryTree(root1, root2);
        inorder(root3);
    }
}

Python3

# Python3 program to find the Maximum
# Binary Tree from two Binary Trees
  
''' A binary tree node has data,
 pointer to left child
and a pointer to right child '''
class Node:
     
    def __init__(self, data, left, right):
         
        self.data = data
        self.left = left
        self.right = right
    
''' Helper method that allocates
   a new node with the given data 
   and None left and right pointers. '''
def newNode(data):
 
    return Node(data, None, None);
  
''' Given a binary tree, print 
   its nodes in inorder'''
def inorder(node):
 
    if (node == None):
        return;
 
    ''' first recur on left child '''
    inorder(node.left);
 
    ''' then print the data of node '''
    print(node.data, end=' ');
 
    ''' now recur on right child '''
    inorder(node.right);
 
''' Method to find the maximum 
   binary tree from
   two binary trees'''
def MaximumBinaryTree(t1, t2):
 
    if (t1 == None):
        return t2;
    if (t2 == None):
        return t1;
    t1.data = max(t1.data, t2.data);
    t1.left = MaximumBinaryTree(t1.left,
                                t2.left);
    t1.right = MaximumBinaryTree(t1.right,
                                 t2.right);
    return t1;
 
# Driver Code
if __name__=='__main__':
     
    ''' First Binary Tree
             3
            / \
           2   6
          /
         20
    '''
 
    root1 = newNode(3);
    root1.left = newNode(2);
    root1.right = newNode(6);
    root1.left.left = newNode(20);
 
    ''' Second Binary Tree
             5
            / \
            1  8
            \   \
              2   8
              '''
    root2 = newNode(5);
    root2.left = newNode(1);
    root2.right = newNode(8);
    root2.left.right = newNode(2);
    root2.right.right = newNode(8);
 
    root3 = MaximumBinaryTree(root1, root2);
    inorder(root3);
 
# This code is contributed by rutvik_56

C#

// C# program to find the Maximum 
// Binary Tree from two Binary Trees 
using System;
 
// A binary tree node has data, 
// pointer to left child 
// and a pointer to right child 
class Node{
     
public int data; 
public Node left, right; 
 
public Node(int data, Node left, 
                      Node right) 
{ 
    this.data = data; 
    this.left = left; 
    this.right = right; 
} 
 
// Helper method that allocates 
// a new node with the given data 
// and NULL left and right pointers. 
static Node newNode(int data) 
{ 
    return new Node(data, null, null); 
} 
 
// Given a binary tree, print 
// its nodes in inorder
static void inorder(Node node) 
{ 
    if (node == null) 
        return; 
 
    // first recur on left child 
    inorder(node.left); 
 
    // then print the data of node 
    Console.Write("{0} ", node.data); 
 
    // now recur on right child 
    inorder(node.right); 
} 
 
// Method to find the maximum 
// binary tree from 
// two binary trees
static Node MaximumBinaryTree(Node t1, Node t2) 
{ 
    if (t1 == null) 
        return t2; 
    if (t2 == null) 
        return t1; 
 
    t1.data = Math.Max(t1.data, t2.data); 
    t1.left = MaximumBinaryTree(t1.left, 
                                t2.left); 
    t1.right = MaximumBinaryTree(t1.right, 
                                 t2.right); 
    return t1; 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
     
    /* First Binary Tree 
             3 
            / \ 
           2   6 
         / 
        20 
    */
 
    Node root1 = newNode(3); 
    root1.left = newNode(2); 
    root1.right = newNode(6); 
    root1.left.left = newNode(20); 
 
    /* Second Binary Tree 
            5 
           / \ 
          1   8 
           \   \ 
            2   8 
            */
    Node root2 = newNode(5); 
    root2.left = newNode(1); 
    root2.right = newNode(8); 
    root2.left.right = newNode(2); 
    root2.right.right = newNode(8); 
 
    Node root3 = MaximumBinaryTree(root1, root2); 
    inorder(root3); 
} 
} 
 
// This code is contributed by Amal Kumar Choubey

Javascript

<script>
 
// Javascript program to find the Maximum 
// Binary Tree from two Binary Trees 
 
// A binary tree node has data, 
// pointer to left child 
// and a pointer to right child 
class Node{
     
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// Helper method that allocates 
// a new node with the given data 
// and NULL left and right pointers. 
function newNode(data) 
{ 
    return new Node(data, null, null); 
} 
 
// Given a binary tree, print 
// its nodes in inorder
function inorder(node) 
{ 
    if (node == null) 
        return; 
 
    // first recur on left child 
    inorder(node.left); 
 
    // then print the data of node 
    document.write(node.data + " "); 
 
    // now recur on right child 
    inorder(node.right); 
} 
 
// Method to find the maximum 
// binary tree from 
// two binary trees
function MaximumBinaryTree(t1, t2) 
{ 
    if (t1 == null) 
        return t2; 
    if (t2 == null) 
        return t1; 
 
    t1.data = Math.max(t1.data, t2.data); 
    t1.left = MaximumBinaryTree(t1.left, 
                                t2.left); 
    t1.right = MaximumBinaryTree(t1.right, 
                                 t2.right); 
    return t1; 
} 
 
// Driver Code 
 
/* First Binary Tree 
         3 
        / \ 
       2   6 
     / 
    20 
*/
var root1 = newNode(3); 
root1.left = newNode(2); 
root1.right = newNode(6); 
root1.left.left = newNode(20); 
/* Second Binary Tree 
        5 
       / \ 
      1   8 
       \   \ 
        2   8 
        */
var root2 = newNode(5); 
root2.left = newNode(1); 
root2.right = newNode(8); 
root2.left.right = newNode(2); 
root2.right.right = newNode(8); 
var root3 = MaximumBinaryTree(root1, root2); 
inorder(root3); 
 
 
</script>

Output:

20 2 2 5 8 8

Time Complexity: O(N)
Auxiliary Space: O(N)

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!