Skip to main content

Find all duplicate subtrees in binary tree

Duplicate Subtree Example

Here given code implementation process.

/*
  Java program
  Find all duplicate subtrees in binary tree
*/
import java.util.HashMap;
import java.util.Map;
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	//Display Inorder view of binary tree
	public void inorder(TreeNode node)
	{
		if (node != null)
		{
			inorder(node.left);
			// Print node value
			System.out.print("  " + node.data);
			inorder(node.right);
		}
	}
	public String findSubTree(TreeNode node, Map <String, Integer> result)
	{
		if (node != null)
		{
			String record = "";
			// Recursively visit left and right subtree
			record += findSubTree(node.left, result);
			record += "(" + node.data + ")";
			record += findSubTree(node.right, result);
			if (result.containsKey(record))
			{
				// When key exists then update value
				result.put(record, result.get(record) + 1);
			}
			else
			{
				// Add new subtree
				result.put(record, 1);
			}
			return record;
		}
		else
		{
			return "";
		}
	}
	public void duplicateSubtree()
	{
		if (this.root == null)
		{
			// When tree is empty
			System.out.print("\n Empty Tree \n");
		}
		// This is used to collecting all sub tree
		Map < String, Integer > result = new HashMap < > ();
      	boolean status = false;
		// Display all tree nodes
		System.out.print("\n  All Tree Nodes \n");
		this.inorder(this.root);
		findSubTree(this.root, result);
      	 	System.out.print("\n Duplicate subtree ");
		//  Display calculated result
		for (String key: result.keySet())
		{
			if (result.get(key) > 1)
			{	
              	status = true;
				System.out.print("\n" + key);
			}
		}
      	if(status == false)
        {
          	System.out.print("\n None \n");
        }
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		Construct Binary Tree
		-----------------------
		       10
		     /    \
		    5      8
		   / \    / \
		  7  13  7   1
		 /      /     \
		1      1       13
		 \      \
		  3      3 
		*/
		//Add TreeNodes
		tree.root = new TreeNode(10);
		tree.root.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(7);
		tree.root.right = new TreeNode(8);
		tree.root.right.right = new TreeNode(1);
		tree.root.right.left = new TreeNode(7);
		tree.root.right.left.left = new TreeNode(1);
		tree.root.right.left.left.right = new TreeNode(3);
		tree.root.left.right = new TreeNode(13);
		tree.root.left.left.left = new TreeNode(1);
		tree.root.left.left.left.right = new TreeNode(3);
		tree.root.right.right.right = new TreeNode(13);
		tree.duplicateSubtree();
	}
}

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
(1)(3)(7)
(1)(3)
(13)
(3)
//Include header file
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

/*
  C++ Program 
  Find all duplicate subtrees in binary tree
*/

//TreeNode of Binary Tree
class TreeNode
{
    public: 
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        //Set TreeNode value
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class BinaryTree
{
    public: 
    TreeNode *root;
    BinaryTree()
    {
        //Set initial tree root to null
        this->root = NULL;
    }
    //Find subtree and its occurrence
    string find_subtree(struct TreeNode *root, unordered_map < string, int > &collection)
    {
        if (root != NULL)
        {
            string subtree = "";
            //Get the result of left subtree
            subtree += find_subtree(root->left, collection);
            //Get subtree element
            subtree += "(" + to_string(root->data) + ")";
            //Get the result of right subtree
            subtree += find_subtree(root->right, collection);
            // When if subtree exists this is increase subtree occurrence, 
            // Otherwise create a new subtree with 1 frequency
            collection[subtree]++;
            return subtree;
        }
        return "";
    }
    //This function are used to handle the request of finding duplicate subtree in given tree
    void duplicate_subtree(struct TreeNode *root)
    {
        //This are used to store result
        unordered_map < string, int > collection;
        
        find_subtree(root, collection);
        //Create iterator
        unordered_map < string, int > ::iterator element;
        //Display duplicate subtree
        for (element = collection.begin(); element != collection.end(); ++element)
        {
            if (element->second > 1)
            {
                cout << "(" << element->first << ")" << endl;
            }
        }
    }
};
int main()
{
    BinaryTree tree = BinaryTree();
    /*
    Construct Binary Tree
    -----------------------
           10
         /    \
        5      8
       / \    / \
      7  13  7   1
     /      /     \
    1      1       13
     \      \
      3      3 
    // Find equal subtree
    */
    //Add TreeNodes
    tree.root = new TreeNode(10);
    tree.root->left = new TreeNode(5);
    tree.root->left->left = new TreeNode(7);
    tree.root->right = new TreeNode(8);
    tree.root->right->right = new TreeNode(1);
    tree.root->right->left = new TreeNode(7);
    tree.root->right->left->left = new TreeNode(1);
    tree.root->right->left->left->right = new TreeNode(3);
    tree.root->left->right = new TreeNode(13);
    tree.root->left->left->left = new TreeNode(1);
    tree.root->left->left->left->right = new TreeNode(3);
    tree.root->right->right->right = new TreeNode(13);
    tree.duplicate_subtree(tree.root);
    return 0;
}

Output

((3))
((1)(3)(7))
((1)(3))
((13))
// Include namespace system
using System;
using System.Collections.Generic;
// Binary Tree node
public class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        this.root = null;
    }
    //Display Inorder view of binary tree
    public void inorder(TreeNode node)
    {
        if (node != null)
        {
            inorder(node.left);
            // Print node value
            Console.Write("  " + node.data);
            inorder(node.right);
        }
    }
    public String findSubTree(TreeNode node, Dictionary < string, int > result)
    {
        if (node != null)
        {
            String record = "";
            // Recursively visit left and right subtree
            record += findSubTree(node.left, result);
            record += "(" + node.data + ")";
            record += findSubTree(node.right, result);
            if (result.ContainsKey(record))
            {
                result[record] += 1;
            }
            else
            {
                result.Add(record, 1);
            }
            return record;
        }
        else
        {
            return "";
        }
    }
    public void duplicateSubtree()
    {
        if (this.root == null)
        {
            // When tree is empty
            Console.Write("\n Empty Tree \n");
        }
        // This is used to collecting all sub tree
        Dictionary < string, int > result = new Dictionary < string, int > ();
        Boolean status = false;
        // Display all tree nodes
        Console.Write("\n  All Tree Nodes \n");
        this.inorder(this.root);
        findSubTree(this.root, result);
        Console.Write("\n Duplicate subtree ");
        //  Display calculated result
        foreach(KeyValuePair < string, int > entry in result)
        {
            if (entry.Value > 1)
            {
                status = true;
                Console.Write("\n " + entry.Key);
            }
        }
        if (status == false)
        {
            Console.Write("\n None \n");
        }
    }
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /*
        Construct Binary Tree
        -----------------------
               10
             /    \
            5      8
           / \    / \
          7  13  7   1
         /      /     \
        1      1       13
         \      \
          3      3 
        */
        //Add TreeNodes
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(7);
        tree.root.right = new TreeNode(8);
        tree.root.right.right = new TreeNode(1);
        tree.root.right.left = new TreeNode(7);
        tree.root.right.left.left = new TreeNode(1);
        tree.root.right.left.left.right = new TreeNode(3);
        tree.root.left.right = new TreeNode(13);
        tree.root.left.left.left = new TreeNode(1);
        tree.root.left.left.left.right = new TreeNode(3);
        tree.root.right.right.right = new TreeNode(13);
        tree.duplicateSubtree();
    }
}

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
 (3)
 (1)(3)
 (1)(3)(7)
 (13)
<?php
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinaryTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//Display Inorder view of binary tree
	public	function inorder($node)
	{
		if ($node != null)
		{
			$this->inorder($node->left);
			// Print node value
			echo "  ". $node->data;
			$this->inorder($node->right);
		}
	}
	public	function findSubTree($node, &$result)
	{
		if ($node != null)
		{
			$record = "";
			// Recursively visit left and right subtree
			$record .= $this->findSubTree($node->left, $result);
			$record .= "(". $node->data .")";
			$record .= $this->findSubTree($node->right, $result);
			if (array_key_exists($record, $result))
			{
				$result[$record] = $result[$record] + 1;
			}
			else
			{
				$result[$record] = 1;
			}
			return $record;
		}
		else
		{
			return "";
		}
	}
	public	function duplicateSubtree()
	{
		if ($this->root == null)
		{
			// When tree is empty
			echo "\n Empty Tree \n";
		}
		// This is used to collecting all sub tree
		$result = array();
		$status = false;
		// Display all tree nodes
		echo "\n  All Tree Nodes \n";
		$this->inorder($this->root);
		$this->findSubTree($this->root, $result);
		echo "\n Duplicate subtree ";
		//  Display calculated result
		foreach($result as $key => $value)
		{
			if ($value > 1)
			{
				$status = true;
				echo "\n ". $key;
			}
		}
		if ($status == false)
		{
			echo "\n None \n";
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	Construct Binary Tree
	-----------------------
	       10
	     /    \
	    5      8
	   / \    / \
	  7  13  7   1
	 /      /     \
	1      1       13
	 \      \
	  3      3 
	*/
	//Add TreeNodes
	$tree->root = new TreeNode(10);
	$tree->root->left = new TreeNode(5);
	$tree->root->left->left = new TreeNode(7);
	$tree->root->right = new TreeNode(8);
	$tree->root->right->right = new TreeNode(1);
	$tree->root->right->left = new TreeNode(7);
	$tree->root->right->left->left = new TreeNode(1);
	$tree->root->right->left->left->right = new TreeNode(3);
	$tree->root->left->right = new TreeNode(13);
	$tree->root->left->left->left = new TreeNode(1);
	$tree->root->left->left->left->right = new TreeNode(3);
	$tree->root->right->right->right = new TreeNode(13);
	$tree->duplicateSubtree();
}
main();

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
 (3)
 (1)(3)
 (1)(3)(7)
 (13)
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	//Display Inorder view of binary tree
	inorder(node)
	{
		if (node != null)
		{
			this.inorder(node.left);
			// Print node value
			process.stdout.write("  " + node.data);
			this.inorder(node.right);
		}
	}
	findSubTree(node,result)
	{
		if (node != null)
		{
			var record = "";
			// Recursively visit left and right subtree
			record += this.findSubTree(node.left, result);
			record += "(" + node.data + ")";
			record += this.findSubTree(node.right, result);
			if (result.has(record))
			{
				result.set(record, result.get(record) + 1);
			}
			else
			{
				result.set(record, 1);
			}
			return record;
		}
		else
		{
			return "";
		}
	}
	duplicateSubtree()
	{
		if (this.root == null)
		{
			// When tree is empty
			process.stdout.write("\n Empty Tree \n");
		}
		// This is used to collecting all sub tree
		var result = new Map();
		var status = false;
		// Display all tree nodes
		process.stdout.write("\n  All Tree Nodes \n");
		this.inorder(this.root);
		this.findSubTree(this.root, result);
		process.stdout.write("\n Duplicate subtree ");
		//  Display calculated result
		for (let [key, value] of result.entries())
		{
			if (value > 1)
			{
				status = true;
				process.stdout.write("\n " + key);
			}
		}
		if (status == false)
		{
			process.stdout.write("\n None \n");
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	Construct Binary Tree
	-----------------------
	       10
	     /    \
	    5      8
	   / \    / \
	  7  13  7   1
	 /      /     \
	1      1       13
	 \      \
	  3      3 
	*/
	//Add TreeNodes
	tree.root = new TreeNode(10);
	tree.root.left = new TreeNode(5);
	tree.root.left.left = new TreeNode(7);
	tree.root.right = new TreeNode(8);
	tree.root.right.right = new TreeNode(1);
	tree.root.right.left = new TreeNode(7);
	tree.root.right.left.left = new TreeNode(1);
	tree.root.right.left.left.right = new TreeNode(3);
	tree.root.left.right = new TreeNode(13);
	tree.root.left.left.left = new TreeNode(1);
	tree.root.left.left.left.right = new TreeNode(3);
	tree.root.right.right.right = new TreeNode(13);
	tree.duplicateSubtree();
}
main();

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
 (3)
 (1)(3)
 (1)(3)(7)
 (13)
#   Python 3 program
#   Find all duplicate subtrees in binary tree

#  Binary Tree node
class TreeNode :
	
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	
	def __init__(self) :
		self.root = None
	
	# Display Inorder view of binary tree
	def inorder(self, node) :
		if (node != None) :
			self.inorder(node.left)
			#  Print node value
			print("  ", node.data, end = "")
			self.inorder(node.right)
		
	
	def findSubTree(self, node, result) :
		if (node != None) :
			record = ""
			#  Recursively visit left and right subtree
			record += self.findSubTree(node.left, result)
			record += "("+ str(node.data) +")"
			record += self.findSubTree(node.right, result)
			if (record in result.keys()) :
				result[record] = result.get(record) + 1
			else :
				result[record] = 1
			
			return record
		else :
			return ""
		
	
	def duplicateSubtree(self) :
		if (self.root == None) :
			#  When tree is empty
			print("\n Empty Tree ")
		
		#  This is used to collecting all sub tree
		result = dict()
		status = False
		#  Display all tree nodes
		print("\n  All Tree Nodes ")
		self.inorder(self.root)
		self.findSubTree(self.root, result)
		print("\n Duplicate subtree ", end = "")
		#   Display calculated result
		for  key, value in result.items():
			if (value > 1) :
				status = True
				print("\n", key, end = "")
			
		
		if (status == False) :
			print("\n None ")
		
	

def main() :
	tree = BinaryTree()
	# 
	# Construct Binary Tree
	# -----------------------
	#        10
	#      /    \
	#     5      8
	#    / \    / \
	#   7  13  7   1
	#  /      /     \
	# 1      1       13
	#  \      \
	#   3      3 
	
	# Add Tree Nodes
	tree.root = TreeNode(10)
	tree.root.left = TreeNode(5)
	tree.root.left.left = TreeNode(7)
	tree.root.right = TreeNode(8)
	tree.root.right.right = TreeNode(1)
	tree.root.right.left = TreeNode(7)
	tree.root.right.left.left = TreeNode(1)
	tree.root.right.left.left.right = TreeNode(3)
	tree.root.left.right = TreeNode(13)
	tree.root.left.left.left = TreeNode(1)
	tree.root.left.left.left.right = TreeNode(3)
	tree.root.right.right.right = TreeNode(13)
	tree.duplicateSubtree()

if __name__ == "__main__": main()

Output

  All Tree Nodes
   1   3   7   5   13   10   1   3   7   8   1   13
 Duplicate subtree
 (13)
 (1)(3)(7)
 (1)(3)
 (3)
#   Ruby program
#   Find all duplicate subtrees in binary tree

#  Binary Tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		self.root = nil
	end

	# Display Inorder view of binary tree
	def inorder(node) 
		if (node != nil) 
			self.inorder(node.left)
			#  Print node value
			print("  ", node.data)
			self.inorder(node.right)
		end

	end

	def findSubTree(node, result) 
		if (node != nil) 
			record = ""
			#  Recursively visit left and right subtree
			record += self.findSubTree(node.left, result)
			record += "(#{node.data})"
			record += self.findSubTree(node.right, result)
			if (result.key?(record)) 
				result[record] = result[record] + 1
			else 
				result[record] = 1
			end

			return record
		else 
			return ""
		end

	end

	def duplicateSubtree() 
		if (self.root == nil) 
			#  When tree is empty
			print("\n Empty Tree \n")
		end

		#  This is used to collecting all sub tree
		result = Hash.new 
		status = false
		#  Display all tree nodes
		print("\n  All Tree Nodes \n")
		self.inorder(self.root)
		self.findSubTree(self.root, result)
		print("\n Duplicate subtree ")
		#   Display calculated result
		result.each{ |key,value|
			if (value > 1) 
				status = true
				print("\n ", key)
			end
        }

		if (status == false) 
			print("\n None \n")
		end

	end

end

def main() 
	tree = BinaryTree.new()
	# 
	# Construct Binary Tree
	# -----------------------
	#        10
	#      /    \
	#     5      8
	#    / \    / \
	#   7  13  7   1
	#  /      /     \
	# 1      1       13
	#  \      \
	#   3      3 
	
	# Add TreeNodes
	tree.root = TreeNode.new(10)
	tree.root.left = TreeNode.new(5)
	tree.root.left.left = TreeNode.new(7)
	tree.root.right = TreeNode.new(8)
	tree.root.right.right = TreeNode.new(1)
	tree.root.right.left = TreeNode.new(7)
	tree.root.right.left.left = TreeNode.new(1)
	tree.root.right.left.left.right = TreeNode.new(3)
	tree.root.left.right = TreeNode.new(13)
	tree.root.left.left.left = TreeNode.new(1)
	tree.root.left.left.left.right = TreeNode.new(3)
	tree.root.right.right.right = TreeNode.new(13)
	tree.duplicateSubtree()
end

main()

Output

  All Tree Nodes 
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree 
 (3)
 (1)(3)
 (1)(3)(7)
 (13)
import scala.collection.mutable.Map;
/*
  Scala program
  Find all duplicate subtrees in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//Display Inorder view of binary tree
	def inorder(node: TreeNode): Unit = {
		if (node != null)
		{
			this.inorder(node.left);
			// Print node value
			print("  " + node.data);
			this.inorder(node.right);
		}
	}
	def findSubTree(node: TreeNode, result: Map[String, Int] ): String = {
		if (node != null)
		{
			var record: String = "";
			// Recursively visit left and right subtree
			record += this.findSubTree(node.left, result);
			record += "(" + node.data + ")";
			record += this.findSubTree(node.right, result);
			if (result.contains(record))
			{
				result(record) = result.get(record).get + 1;
			}
			else
			{
				result(record) = 1;
			}
			return record;
		}
		else
		{
			return "";
		}
	}
	def duplicateSubtree(): Unit = {
		if (this.root == null)
		{
			// When tree is empty
			print("\n Empty Tree \n");
		}
		// This is used to collecting all sub tree
	
		var result: Map[String, Int] = Map();
		var status: Boolean = false;
		// Display all tree nodes
		print("\n  All Tree Nodes \n");
		this.inorder(this.root);
		this.findSubTree(this.root, result);
		print("\n Duplicate subtree ");
		//  Display calculated result
		result.keys.foreach
		{    key =>
			if (result(key) > 1)
			{
				status = true;
				print("\n " + key);
			}
		}
		if (status == false)
		{
			print("\n None \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		Construct Binary Tree
		-----------------------
		       10
		     /    \
		    5      8
		   / \    / \
		  7  13  7   1
		 /      /     \
		1      1       13
		 \      \
		  3      3 
		*/
		//Add TreeNodes
		tree.root = new TreeNode(10);
		tree.root.left = new TreeNode(5);
		tree.root.left.left = new TreeNode(7);
		tree.root.right = new TreeNode(8);
		tree.root.right.right = new TreeNode(1);
		tree.root.right.left = new TreeNode(7);
		tree.root.right.left.left = new TreeNode(1);
		tree.root.right.left.left.right = new TreeNode(3);
		tree.root.left.right = new TreeNode(13);
		tree.root.left.left.left = new TreeNode(1);
		tree.root.left.left.left.right = new TreeNode(3);
		tree.root.right.right.right = new TreeNode(13);
		tree.duplicateSubtree();
	}
}

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
 (1)(3)(7)
 (1)(3)
 (13)
 (3)
/*
  Swift 4 program
  Find all duplicate subtrees in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	//Display Inorder view of binary tree
	func inorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.inorder(node!.left);
			// Print node value
			print("  ", node!.data, terminator: "");
			self.inorder(node!.right);
		}
	}
	func findSubTree(_ node: TreeNode? ,_ result : inout [String : Int])->String
	{
		if (node  != nil)
		{
			var record: String = "";
			// Recursively visit left and right subtree
			record += self.findSubTree(node!.left, &result);
			record += "(\(String(node!.data)))";
			record += self.findSubTree(node!.right, &result);
			if (result.keys.contains(record))
			{
				result[record] = result[record]! + 1;
			}
			else
			{
				result[record] = 1;
			}
			return record;
		}
		else
		{
			return "";
		}
	}
	func duplicateSubtree()
	{
		if (self.root == nil)
		{
			// When tree is empty
			print("\n Empty Tree ");
		}
		// This is used to collecting all sub tree
		var result = [String : Int]();
		var status: Bool = false;
		// Display all tree nodes
		print("\n  All Tree Nodes ");
		self.inorder(self.root);
		let _ = self.findSubTree(self.root, &result);
		print("\n Duplicate subtree ", terminator: "");
		//  Display calculated result
		for (key, value) in result
		{
			if (value > 1)
			{
				status = true;
				print("\n  ", key, terminator: "");
			}
		}
		if (status == false)
		{
			print("\n None ");
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	Construct Binary Tree
	-----------------------
	       10
	     /    \
	    5      8
	   / \    / \
	  7  13  7   1
	 /      /     \
	1      1       13
	 \      \
	  3      3 
	*/
	//Add TreeNodes
	tree.root = TreeNode(10);
	tree.root!.left = TreeNode(5);
	tree.root!.left!.left = TreeNode(7);
	tree.root!.right = TreeNode(8);
	tree.root!.right!.right = TreeNode(1);
	tree.root!.right!.left = TreeNode(7);
	tree.root!.right!.left!.left = TreeNode(1);
	tree.root!.right!.left!.left!.right = TreeNode(3);
	tree.root!.left!.right = TreeNode(13);
	tree.root!.left!.left!.left = TreeNode(1);
	tree.root!.left!.left!.left!.right = TreeNode(3);
	tree.root!.right!.right!.right = TreeNode(13);
	tree.duplicateSubtree();
}
main();

Output

  All Tree Nodes
   1   3   7   5   13   10   1   3   7   8   1   13
 Duplicate subtree
   (1)(3)(7)
   (3)
   (13)
   (1)(3)
/*
  Kotlin program
  Find all duplicate subtrees in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	//Display Inorder view of binary tree
	fun inorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			this.inorder(node.left);
			// Print node value
			print("  " + node.data);
			this.inorder(node.right);
		}
	}
	fun findSubTree(node: TreeNode ? ,result : MutableMap <String,Int> ): String
	{
		if (node != null)
		{
			var record: String = "";
			// Recursively visit left and right subtree
			record += this.findSubTree(node.left, result);
			record += "(" + node.data + ")";
			record += this.findSubTree(node.right, result);
			if (result.containsKey(record))
			{
				result.put(record, result.getValue(record) + 1);
			}
			else
			{
				result.put(record, 1);
			}
			return record;
		}
		else
		{
			return "";
		}
	}
	fun duplicateSubtree(): Unit
	{
		if (this.root == null)
		{
			// When tree is empty
			print("\n Empty Tree \n");
		}
		// This is used to collecting all sub tree
		var result = mutableMapOf<String, Int>();
		var status: Boolean = false;
		// Display all tree nodes
		print("\n  All Tree Nodes \n");
		this.inorder(this.root);
		this.findSubTree(this.root, result);
		print("\n Duplicate subtree ");
		//  Display calculated result
		for( (key, value) in result )
		{
			if (value > 1)
			{
				status = true;
				print("\n  " + key);
			}
		}
		if (status == false)
		{
			print("\n None \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var tree: BinaryTree = BinaryTree();
	/*
	Construct Binary Tree
	-----------------------
	       10
	     /    \
	    5      8
	   / \    / \
	  7  13  7   1
	 /      /     \
	1      1       13
	 \      \
	  3      3 
	*/
	//Add TreeNodes
	tree.root = TreeNode(10);
	tree.root?.left = TreeNode(5);
	tree.root?.left?.left = TreeNode(7);
	tree.root?.right = TreeNode(8);
	tree.root?.right?.right = TreeNode(1);
	tree.root?.right?.left = TreeNode(7);
	tree.root?.right?.left?.left = TreeNode(1);
	tree.root?.right?.left?.left?.right = TreeNode(3);
	tree.root?.left?.right = TreeNode(13);
	tree.root?.left?.left?.left = TreeNode(1);
	tree.root?.left?.left?.left?.right = TreeNode(3);
	tree.root?.right?.right?.right = TreeNode(13);
	tree.duplicateSubtree();
}

Output

  All Tree Nodes
  1  3  7  5  13  10  1  3  7  8  1  13
 Duplicate subtree
  (3)
  (1)(3)
  (1)(3)(7)
  (13)
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment