Tutorialspoint.dev

Find first non matching leaves in two binary trees

Given two binary trees, find first leaves of two trees that do not match. If there are no non-matching leaves, print nothing.

Examples:

Input : First Tree
          5
        /   
       2     7
     /   
   10     11

      Second Tree   
          6
       /    
     10     15

Output : 11 15
If we consider leaves of two trees in order,
we can see that 11 and 15 are the first leaves 
that do not match.

Method 1 (Simple) :
Do Inorder traversal of both trees one by one, store the leaves of both trees in two different lists. Finally find first values which are different in both lists. Time complexity is O(n1 + n2) where n1 and n2 are number of nodes in two trees. Auxiliary space requirement is O(n1 + n2).

Method 2 (Efficient)
This solution auxiliary space requirement as O(h1 + h2) where h1 and h2 are heights of trees. We do Iterative Preorder traversal of both the trees simultaneously using stacks. We maintain a stack for each tree. For every tree, keep pushing nodes in the stack till the top node is a leaf node. Compare the two top nodes f both the stack. If they are equal, do further traversal else return.

C++

// C++ program to find first leaves that are
// not same.
#include<bits/stdc++.h>
using namespace std;
  
// Tree node
struct Node
{
    int data;
    Node *left,  *right;
};
  
// Utility method to create a new node
Node *newNode(int x)
{
    Node * temp = new Node;
    temp->data = x;
    temp->left = temp->right = NULL;
    return temp;
}
  
bool isLeaf(Node * t)
{
    return ((t->left == NULL) && (t->right == NULL));
}
  
// Prints the first non-matching leaf node in
// two trees if it exists, else prints nothing.
void findFirstUnmatch(Node *root1, Node *root2)
{
    // If any of the tree is empty
    if (root1 == NULL || root2 == NULL)
      return;
  
    // Create two stacks for preorder traversals
    stack<Node*> s1, s2;
    s1.push(root1);
    s2.push(root2);
  
    while (!s1.empty() || !s2.empty())
    {
        // If traversal of one tree is over
        // and other tree still has nodes.
        if (s1.empty() || s2.empty() )
           return;
  
        // Do iterative traversal of first tree
        // and find first lead node in it as "temp1"
        Node *temp1 = s1.top();
        s1.pop();
        while (temp1 && !isLeaf(temp1))
        {
            // pushing right childfirst so that
            // left child comes first while popping.
            s1.push(temp1->right);
            s1.push(temp1->left);
            temp1 = s1.top();
            s1.pop();
        }
  
        // Do iterative traversal of second tree
        // and find first lead node in it as "temp2"
        Node * temp2 = s2.top();
        s2.pop();
        while (temp2 && !isLeaf(temp2))
        {
            s2.push(temp2->right);
            s2.push(temp2->left);
            temp2 = s2.top();
            s2.pop();
        }
  
        // If we found leaves in both trees
        if (temp1 != NULL && temp2 != NULL )
        {
            if (temp1->data != temp2->data )
            {
                cout << "First non matching leaves : "
                     << temp1->data <<"  "<< temp2->data
                     << endl;
                return;
            }
        }
    }
}
  
// Driver code
int main()
{
    struct Node *root1 = newNode(5);
    root1->left = newNode(2);
    root1->right = newNode(7);
    root1->left->left = newNode(10);
    root1->left->right = newNode(11);
  
    struct Node * root2 = newNode(6);
    root2->left = newNode(10);
    root2->right = newNode(15);
  
    findFirstUnmatch(root1,root2);
  
    return 0;
}

Java

// Java program to find first leaves that are 
// not same. 
import java.util.*;
class GfG {
  
// Tree node 
static class Node 
    int data; 
    Node left, right; 
}
  
// Utility method to create a new node 
static Node newNode(int x) 
    Node temp = new Node(); 
    temp.data = x; 
    temp.left = null;
    temp.right = null
    return temp; 
  
static boolean isLeaf(Node t) 
    return ((t.left == null) && (t.right == null)); 
  
// Prints the first non-matching leaf node in 
// two trees if it exists, else prints nothing. 
static void findFirstUnmatch(Node root1, Node root2) 
    // If any of the tree is empty 
    if (root1 == null || root2 == null
    return
  
    // Create two stacks for preorder traversals 
    Stack<Node> s1 = new Stack<Node> ();
    Stack<Node> s2 = new Stack<Node> (); 
    s1.push(root1); 
    s2.push(root2); 
  
    while (!s1.isEmpty() || !s2.isEmpty()) 
    
        // If traversal of one tree is over 
        // and other tree still has nodes. 
        if (s1.isEmpty() || s2.isEmpty() ) 
        return
  
        // Do iterative traversal of first tree 
        // and find first lead node in it as "temp1" 
        Node temp1 = s1.peek(); 
        s1.pop(); 
        while (temp1 != null && isLeaf(temp1) != true
        
            // pushing right childfirst so that 
            // left child comes first while popping. 
            s1.push(temp1.right); 
            s1.push(temp1.left); 
            temp1 = s1.peek(); 
            s1.pop(); 
        
  
        // Do iterative traversal of second tree 
        // and find first lead node in it as "temp2" 
        Node temp2 = s2.peek(); 
        s2.pop(); 
        while (temp2 != null && isLeaf(temp2) != true
        
            s2.push(temp2.right); 
            s2.push(temp2.left); 
            temp2 = s2.peek(); 
            s2.pop(); 
        
  
        // If we found leaves in both trees 
        if (temp1 != null && temp2 != null
        
            if (temp1.data != temp2.data ) 
            
                System.out.println(temp1.data+" "+temp2.data); 
                return
            
        
    
  
// Driver code 
public static void main(String[] args) 
    Node root1 = newNode(5); 
    root1.left = newNode(2); 
    root1.right = newNode(7); 
    root1.left.left = newNode(10); 
    root1.left.right = newNode(11); 
  
    Node root2 = newNode(6); 
    root2.left = newNode(10); 
    root2.right = newNode(15); 
  
    findFirstUnmatch(root1,root2); 
  

Python3

# Python3 program to find first leaves 
# that are not same.
  
# Tree Node
# Utility function to create a 
# new tree Node 
class newNode: 
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
          
def isLeaf(t): 
  
    return ((t.left == None) and 
            (t.right == None)) 
  
# Prints the first non-matching leaf node in 
# two trees if it exists, else prints nothing. 
def findFirstUnmatch(root1, root2) :
  
    # If any of the tree is empty 
    if (root1 == None or root2 == None) :
        return
  
    # Create two stacks for preorder
    # traversals 
    s1 = []
    s2 = [] 
    s1.insert(0, root1) 
    s2.insert(0, root2) 
  
    while (len(s1) or len(s2)) :
      
        # If traversal of one tree is over 
        # and other tree still has nodes. 
        if (len(s1) == 0 or len(s2) == 0) :
            return
  
        # Do iterative traversal of first 
        # tree and find first lead node 
        # in it as "temp1" 
        temp1 = s1[0
        s1.pop(0
        while (temp1 and not isLeaf(temp1)) :
          
            # pushing right childfirst so that 
            # left child comes first while popping. 
            s1.insert(0, temp1.right) 
            s1.insert(0, temp1.left) 
            temp1 = s1[0
            s1.pop(0
          
        # Do iterative traversal of second tree 
        # and find first lead node in it as "temp2" 
        temp2 = s2[0]
        s2.pop(0
        while (temp2 and not isLeaf(temp2)) :
          
            s2.insert(0, temp2.right) 
            s2.insert(0, temp2.left) 
            temp2 = s2[0]
            s2.pop(0
          
        # If we found leaves in both trees 
        if (temp1 != None and temp2 != None ) :
          
            if (temp1.data != temp2.data ) :
              
                print("First non matching leaves :",
                        temp1.data, "", temp2.data ) 
                return
  
# Driver Code 
if __name__ == '__main__':
    root1 = newNode(5
    root1.left = newNode(2
    root1.right = newNode(7
    root1.left.left = newNode(10
    root1.left.right = newNode(11
  
    root2 = newNode(6
    root2.left = newNode(10
    root2.right = newNode(15
  
    findFirstUnmatch(root1,root2)
  
# This code is contributed by
# SHUBHAMSINGH10

C#

// C# program to find first leaves that are 
// not same. 
using System;
using System.Collections.Generic;
  
class GfG 
{
  
    // Tree node 
    public class Node 
    
        public int data; 
        public Node left, right; 
    }
  
    // Utility method to create a new node 
    static Node newNode(int x) 
    
        Node temp = new Node(); 
        temp.data = x; 
        temp.left = null;
        temp.right = null
        return temp; 
    
  
    static bool isLeaf(Node t) 
    
        return ((t.left == null) && (t.right == null)); 
    
  
    // Prints the first non-matching leaf node in 
    // two trees if it exists, else prints nothing. 
    static void findFirstUnmatch(Node root1, Node root2) 
    
        // If any of the tree is empty 
        if (root1 == null || root2 == null
        return
  
        // Create two stacks for preorder traversals 
        Stack<Node> s1 = new Stack<Node> ();
        Stack<Node> s2 = new Stack<Node> (); 
        s1.Push(root1); 
        s2.Push(root2); 
  
        while (s1.Count != 0 || s2.Count != 0) 
        
            // If traversal of one tree is over 
            // and other tree still has nodes. 
            if (s1.Count == 0 || s2.Count == 0 ) 
            return
  
            // Do iterative traversal of first tree 
            // and find first lead node in it as "temp1" 
            Node temp1 = s1.Peek(); 
            s1.Pop(); 
            while (temp1 != null && isLeaf(temp1) != true
            
                // pushing right childfirst so that 
                // left child comes first while popping. 
                s1.Push(temp1.right); 
                s1.Push(temp1.left); 
                temp1 = s1.Peek(); 
                s1.Pop(); 
            
  
            // Do iterative traversal of second tree 
            // and find first lead node in it as "temp2" 
            Node temp2 = s2.Peek(); 
            s2.Pop(); 
            while (temp2 != null && isLeaf(temp2) != true
            
                s2.Push(temp2.right); 
                s2.Push(temp2.left); 
                temp2 = s2.Peek(); 
                s2.Pop(); 
            
  
            // If we found leaves in both trees 
            if (temp1 != null && temp2 != null
            
                if (temp1.data != temp2.data ) 
                
                    Console.WriteLine(temp1.data + " " + temp2.data); 
                    return
                
            
        
    
  
    // Driver code 
    public static void Main(String[] args) 
    
        Node root1 = newNode(5); 
        root1.left = newNode(2); 
        root1.right = newNode(7); 
        root1.left.left = newNode(10); 
        root1.left.right = newNode(11); 
  
        Node root2 = newNode(6); 
        root2.left = newNode(10); 
        root2.right = newNode(15); 
  
        findFirstUnmatch(root1,root2); 
  
    
  
// This code has been contributed by 29AjayKumar


Output:



First non matching leaves : 11  15

References:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter