Binary tree, Subtree - Naukri Code 360

Introduction

To check if a binary tree contains duplicate subtrees of size 2 or more is a basic binary tree problem. It had been asked in the Google, Optum, and Credit Suisse interview round for the role of software engineers/developers. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach of the programmer.

In this article, we’ll solve this problem by using two approaches, the first is by using in-order and post-order traversal, and the second is by using a tree serialisation and hashing approach.

Problem Statement

We are given a binary tree. We are supposed to check whether the given binary tree contains a duplicate subtree of size 2 or more. Subtree means any node and its descendants.

Duplicate subtree means whether there is a common similar subtree set present on either the left or right side of the root.

Sample Examples

Input-1:

Output:

Explanation: In the above example, the left children of the node ‘1’, i.e. {2,4,5} are getting their value repeated at the right child of the node ‘3’.

Input-2:

Output:

Explanation: In the above example, the right children of the node ‘Q’, i.e. {T, V, W} are getting their value repeated at the right child of the node ‘R’.

Approach 1(In-order and Post-order Traversal)

In this approach, the concept is to follow in-order and post-order traversal. When we find a duplicate subtree, we will return true else; we will return false.

So let’s see the implementation of this method now.

Algorithm

We will first create a data structure to store a binary tree node.
Afterward, we will create a function to store in-order traversal on the tree in a vector.
After creating a function of in-order traversal, we will create a function to store postorder traversal on the tree in a vector.
Now we will do in-order and post-order traversal of the trees in order to find whether there are any duplicate subtrees or not.
End

Implementation

C++
Java
Python
Javascript
C#

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// Data structure in order to store a binary tree node
struct Node
{
    int data;
    Node *left, *right;
 
    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};
 
// Function to store inorder traversal on the tree in a vector
void inorderfxn(Node* node, vector<int> &vc)
{
    if (node == nullptr) {
        return;
    }
 
    inorderfxn(node->left, vc);
    vc.push_back(node->data);
    inorderfxn(node->right, vc);
}
 
// Function to store postorder traversal on the tree in a vector
void postorderfxn(Node* node, vector<int> &vc)
{
    if (node == nullptr) {
        return;
    }
 
    postorderfxn(node->left, vc);
    postorderfxn(node->right, vc);
    vc.push_back(node->data);
}
 
// Function in order to check if a given binary tree is a subtree of another
// binary tree or not
bool checkingSubtree(Node* tree, Node* subtree)
{
    // base case: both trees are the same
    if (tree == subtree) {
        return true;
    }
 
    // base case: if the first tree is empty but the second tree is non-empty
    if (tree == nullptr) {
        return false;
    }
 
    // store inorder traversal of both trees in `first` and `second`, respectively
    vector<int> first, second;
    inorderfxn(tree, first);
    inorderfxn(subtree, second);
 
    // return false if `second` is not a subarray of `first`
    auto it = search(first.begin(), first.end(), second.begin(), second.end());
    if (it == first.end()) {
        return false;
    }
 
    // reset both vectors
    first.erase(first.begin(), first.end());
    second.erase(second.begin(), second.end());
 
    // Now store postorder traversal of both trees in `first` and `second`,
    // respectively
    postorderfxn(tree, first);
    postorderfxn(subtree, second);
 
    // return false if `second` is not a subarray of `first`
    it = search(first.begin(), first.end(), second.begin(), second.end());
    if (it == first.end()) {
        return false;
    }
 
    return true;
}
 
int main()
{
  
    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('2');
    root->right->right->right = new Node('5');
    root->right->right->left= new Node('4');


 
    checkingSubtree(root, root->right)? cout << "Yes, the binary tree contains duplicate subtree of size 2 or more": cout << "No, the binary tree contains duplicate subtree of size 2 or more";
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;
import java.util.List;

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

public class BinaryTree {

    public static void inorderTraversal(Node node, List<Integer> list) {
        if (node == null) return;

        inorderTraversal(node.left, list);
        list.add(node.data);
        inorderTraversal(node.right, list);
    }

    public static void postorderTraversal(Node node, List<Integer> list) {
        if (node == null) return;

        postorderTraversal(node.left, list);
        postorderTraversal(node.right, list);
        list.add(node.data);
    }

    public static boolean isSubtree(Node tree, Node subtree) {
        if (tree == subtree) return true;
        if (tree == null) return false;

        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        inorderTraversal(tree, first);
        inorderTraversal(subtree, second);

        if (!first.containsAll(second)) return false;

        first.clear();
        second.clear();
        postorderTraversal(tree, first);
        postorderTraversal(subtree, second);

        return first.containsAll(second);
    }

    public 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(2);
        root.right.right.left = new Node(4);
        root.right.right.right = new Node(5);

        boolean result = isSubtree(root, root.right);
        System.out.println(result ? "Yes, the binary tree contains duplicate subtree of size 2 or more" : "No, the binary tree contains duplicate subtree of size 2 or more");
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

def inorder_traversal(node, lst):
    if node is None:
        return
    inorder_traversal(node.left, lst)
    lst.append(node.data)
    inorder_traversal(node.right, lst)

def postorder_traversal(node, lst):
    if node is None:
        return
    postorder_traversal(node.left, lst)
    postorder_traversal(node.right, lst)
    lst.append(node.data)

def is_subtree(tree, subtree):
    if tree == subtree:
        return True
    if tree is None:
        return False

    first, second = [], []
    inorder_traversal(tree, first)
    inorder_traversal(subtree, second)

    if not all(elem in first for elem in second):
        return False

    first.clear()
    second.clear()
    postorder_traversal(tree, first)
    postorder_traversal(subtree, second)

    return all(elem in first for elem in second)

if __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(2)
    root.right.right.left = Node(4)
    root.right.right.right = Node(5)

    result = is_subtree(root, root.right)
    print("Yes, the binary tree contains duplicate subtree of size 2 or more" if result else "No, the binary tree contains duplicate subtree of size 2 or more")

You can also try this code with Online Python Compiler

Run Code

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.left = this.right = null;
    }
}

function inorderTraversal(node, list) {
    if (node === null) return;

    inorderTraversal(node.left, list);
    list.push(node.data);
    inorderTraversal(node.right, list);
}

function postorderTraversal(node, list) {
    if (node === null) return;

    postorderTraversal(node.left, list);
    postorderTraversal(node.right, list);
    list.push(node.data);
}

function isSubtree(tree, subtree) {
    if (tree === subtree) return true;
    if (tree === null) return false;

    let first = [];
    let second = [];
    inorderTraversal(tree, first);
    inorderTraversal(subtree, second);

    if (!second.every(val => first.includes(val))) return false;

    first = [];
    second = [];
    postorderTraversal(tree, first);
    postorderTraversal(subtree, second);

    return second.every(val => first.includes(val));
}

const 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(2);
root.right.right.left = new Node(4);
root.right.right.right = new Node(5);

const result = isSubtree(root, root.right);
console.log(result ? "Yes, the binary tree contains duplicate subtree of size 2 or more" : "No, the binary tree contains duplicate subtree of size 2 or more");

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class Node
{
    public int Data;
    public Node Left, Right;

    public Node(int data)
    {
        this.Data = data;
        this.Left = this.Right = null;
    }
}

class BinaryTree
{
    public static void InorderTraversal(Node node, List<int> list)
    {
        if (node == null) return;

        InorderTraversal(node.Left, list);
        list.Add(node.Data);
        InorderTraversal(node.Right, list);
    }

    public static void PostorderTraversal(Node node, List<int> list)
    {
        if (node == null) return;

        PostorderTraversal(node.Left, list);
        PostorderTraversal(node.Right, list);
        list.Add(node.Data);
    }

    public static bool IsSubtree(Node tree, Node subtree)
    {
        if (tree == subtree) return true;
        if (tree == null) return false;

        List<int> first = new List<int>();
        List<int> second = new List<int>();
        InorderTraversal(tree, first);
        InorderTraversal(subtree, second);

        if (!IsSublist(first, second)) return false;

        first.Clear();
        second.Clear();
        PostorderTraversal(tree, first);
        PostorderTraversal(subtree, second);

        return IsSublist(first, second);
    }

    private static bool IsSublist(List<int> first, List<int> second)
    {
        if (second.Count == 0) return true;
        if (first.Count < second.Count) return false;

        for (int i = 0; i <= first.Count - second.Count; i++)
        {
            if (first.GetRange(i, second.Count).Equals(second))
            {
                return true;
            }
        }
        return false;
    }

    public 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(2);
        root.Right.Right.Left = new Node(4);
        root.Right.Right.Right = new Node(5);

        bool result = IsSubtree(root, root.Right);
        Console.WriteLine(result ? "Yes, the binary tree contains duplicate subtree of size 2 or more" : "No, the binary tree contains duplicate subtree of size 2 or more");
    }
}

Output:

Time Complexity

The time complexity of the in-order and post-order traversal approach is O(n²), as we are using in-order and post-order traversal. Here ‘n’ represents the number of nodes in a binary tree.

Space Complexity

The auxiliary space used by this program is O(n), hence the space complexity is O(n).

Approach 2(Tree Serialisation and Hashing )

In the approach, the concept is to serialize subtrees as strings and store them in a hash table. We return true if we find a serialized tree (that is not a leaf) that already exists in the hash table.

So let’s see the implementation of this method now.

Algorithm

There are two tasks to complete in order to solve this program. The first step is to find the serialization of the tree, and the second step is to create the hashing table.
In order to do the serialization, we’ll first make the binary tree from root to leaf nodes.
Afterward, we will make a hash table to store the value of the nodes.
Now we will check whether the values of the hash table get matched again or not.
If the values of the hash table are the same, then we will return that there is a duplicate subtree in the array; otherwise, we will return there is not.

Implementation

C++
Java
Python
Javascript
C#

C++

#include<bits/stdc++.h>
using namespace std;
unordered_set<string> sub_tree;

struct Node
	{
 	 char key;
 	 Node *left;
 	 Node *right;
	};

// creating a new node
Node* newNode(char key)
	{
	  Node* node = new Node;
	  node->key = key;
	  node->left = node->right = NULL;
	  return node;
	}

//function to return if size>3
string Search(Node *root)
	{
	  string s = "";
  
	  //if null return separator
	  if (root == NULL)
	    return s + '$';

	  // If left & right subtree has a duplicate subtree.
	  string left_Sub = Search(root->left);
	  if (left_Sub.compare(s) == 0)
	  return s;
	  string right_sub = Search(root->right);
	  if (right_sub.compare(s) == 0)
	  return s;

	  // Serialize current subtree
	  s = s + root->key + left_Sub + right_sub;

	  // If the current subtree is already in the hash table size of a serialize tree with single node is 3 as it has 2 separator nodes.
	  if (s.length() > 3 && sub_tree.find(s) != sub_tree.end())
	  return "";

	  sub_tree.insert(s);
	  return s;
	}


int main()
	{
	  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('2');
	  root->right->right->right = newNode('5');
	  root->right->right->left= newNode('4');

	  string str = Search(root);

	  if(str.compare("") == 0)
    	  cout << Yes, the binary tree contains duplicate subtree of size 2 or more"<<endl;
	  else
    	  cout << " No, the binary tree contains duplicate subtree of size 2 or more" ; 
      return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.HashSet;
import java.util.Set;

class Node {
    char key;
    Node left, right;

    Node(char key) {
        this.key = key;
        this.left = this.right = null;
    }
}

public class BinaryTree {
    static Set<String> sub_tree = new HashSet<>();

    public static Node newNode(char key) {
        Node node = new Node(key);
        return node;
    }

    public static String search(Node root) {
        String s = "";
        if (root == null)
            return s + '$';

        String leftSub = search(root.left);
        if (leftSub.equals(s))
            return s;

        String rightSub = search(root.right);
        if (rightSub.equals(s))
            return s;

        s = s + root.key + leftSub + rightSub;

        if (s.length() > 3 && sub_tree.contains(s))
            return "";

        sub_tree.add(s);
        return s;
    }

    public 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('2');
        root.right.right.left = newNode('4');
        root.right.right.right = newNode('5');

        String str = search(root);

        if (str.equals(""))
            System.out.println("Yes, the binary tree contains duplicate subtree of size 2 or more");
        else
            System.out.println("No, the binary tree contains duplicate subtree of size 2 or more");
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

sub_tree = set()

def new_node(key):
    return Node(key)

def search(root):
    s = ""
    if root is None:
        return s + '$'

    left_sub = search(root.left)
    if left_sub == s:
        return s

    right_sub = search(root.right)
    if right_sub == s:
        return s

    s = s + root.key + left_sub + right_sub

    if len(s) > 3 and s in sub_tree:
        return ""

    sub_tree.add(s)
    return s

if __name__ == "__main__":
    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('2')
    root.right.right.left = new_node('4')
    root.right.right.right = new_node('5')

    str = search(root)

    if str == "":
        print("Yes, the binary tree contains duplicate subtree of size 2 or more")
    else:
        print("No, the binary tree contains duplicate subtree of size 2 or more")

You can also try this code with Online Python Compiler

Run Code

Javascript

class Node {
    constructor(key) {
        this.key = key;
        this.left = this.right = null;
    }
}

const sub_tree = new Set();

function newNode(key) {
    return new Node(key);
}

function search(root) {
    let s = "";
    if (root === null)
        return s + '$';

    let leftSub = search(root.left);
    if (leftSub === s)
        return s;

    let rightSub = search(root.right);
    if (rightSub === s)
        return s;

    s = s + root.key + leftSub + rightSub;

    if (s.length > 3 && sub_tree.has(s))
        return "";

    sub_tree.add(s);
    return s;
}

const 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('2');
root.right.right.left = newNode('4');
root.right.right.right = newNode('5');

const str = search(root);

if (str === "")
    console.log("Yes, the binary tree contains duplicate subtree of size 2 or more");
else
    console.log("No, the binary tree contains duplicate subtree of size 2 or more");

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class Node
{
    public char Key;
    public Node Left, Right;

    public Node(char key)
    {
        this.Key = key;
        this.Left = this.Right = null;
    }
}

class BinaryTree
{
    static HashSet<string> sub_tree = new HashSet<string>();

    public static Node NewNode(char key)
    {
        return new Node(key);
    }

    public static string Search(Node root)
    {
        string s = "";
        if (root == null)
            return s + '$';

        string leftSub = Search(root.Left);
        if (leftSub.Equals(s))
            return s;

        string rightSub = Search(root.Right);
        if (rightSub.Equals(s))
            return s;

        s = s + root.Key + leftSub + rightSub;

        if (s.Length > 3 && sub_tree.Contains(s))
            return "";

        sub_tree.Add(s);
        return s;
    }

    public 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('2');
        root.Right.Right.Left = NewNode('4');
        root.Right.Right.Right = NewNode('5');

        string str = Search(root);

        if (str.Equals(""))
            Console.WriteLine("Yes, the binary tree contains duplicate subtree of size 2 or more");
        else
            Console.WriteLine("No, the binary tree contains duplicate subtree of size 2 or more");
    }
}

Output

Time Complexity

The time complexity to serialise and deserialise a binary tree is linear, i.e., O(n), and the time complexity of using a hash table is also linear. Hence, the time complexity of this approach would be O(n).

Space Complexity

The space complexity of the tree serialisation and hashing approach is O(n), as we are using the concept of hashing table in the program.

Frequently Asked Questions

What is duplicate subtree?

A duplicate subtree in a binary tree is a subtree that appears more than once with the same structure and node values.

How do you remove duplicate subtree?

To remove duplicate subtrees, traverse the tree, serialize each subtree, and use a hash set to identify and eliminate duplicates.

How to find duplicate subtrees in binary tree?

Serialize each subtree during traversal, store these serializations in a hash set, and check for duplicates to find duplicate subtrees.

How do you check if a binary tree is a subtree of another binary tree?

Serialize the inorder and postorder traversals of both trees and check if the subtree's serializations are subarrays of the main tree's serializations.

Can a binary search tree have duplicates?

Typically, binary search trees do not allow duplicate values to ensure that each element can be uniquely positioned based on its value.

Conclusion

This article extensively discussed the problem, to check if a binary tree contains duplicate subtrees of size 2 or more by using in-order and post-order traversal approach and a tree serialization and hashing approach.

We hope this blog has helped you enhance your knowledge regarding binary tree problems. After reading about the program to check if a binary tree contains duplicate subtrees of size 2 or more, are you not feeling excited to read/explore more articles on this topic?

Check out our articles

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More

Introduction

Problem Statement

Sample Examples

Approach 1(In-order and Post-order Traversal)

Algorithm

Implementation

C++

Java

Python

Javascript

C#

Time Complexity

Space Complexity

Approach 2(Tree Serialisation and Hashing )

Algorithm

Implementation

C++

Java

Python

Javascript

C#

Time Complexity

Space Complexity

Frequently Asked Questions

What is duplicate subtree?

How do you remove duplicate subtree?

How to find duplicate subtrees in binary tree?

How do you check if a binary tree is a subtree of another binary tree?

Can a binary search tree have duplicates?

Conclusion