Subtree of binary search tree implementation

subtree of binary search tree

We learned basics of binary search tree and it’s properties and attributes. Today, we will discuss an interesting problem : to find if a given BST is subtree of binary search tree? When does tree becomes subtree of binary search tree? When  all nodes in smaller tree are present in bigger one and in the same order, then we call smaller tree as subtree of bigger tree.

Below figures define what qualifies as subtree and not a subtree

subtree of binary search tree
S is not subtree of tree T
subtree of binary search tree example
S is subtree of T

To find if a tree is subtree of a given tree, we have to find where does subtree lies in bigger tree. Start with roots of both trees and check nodes are equal, if yes, check if left subtree and right subtree of smaller tree are identical to left subtree and right subtree of bigger tree.

If nodes are not equal or any of the subtree is not identical, we move down to left or right of bigger tree and start the process again.

In this procedure, we are comparing root first, then left subtree and in last right subtree. It’s a preorder traversal. There are two preorder traversal involved. One of the bigger tree for selecting the candidate root and other of both trees simultaneously to check if they are identical. While traversing, instead of printing nodes, compare them and see if they are identical or not. Please refer : how to check if two trees are identical or not?

Algorithm to find if tree is subtree of binary search tree

1. Start from root of tree1 and tree2 call them currentNodes
2. If both are null, return true
3. Check if currentNodes are identical?
   3.1 Check if data in currentNodes of both tree is equal.
   3.2 Recursively, check if left and right subtree are identical
   3.3 If 3.1 and 3.2 are true, return true else false
4. If currentNodes are not identical
   4.1 Move down to left subtree of tree1 and repeat 3
   4.2 Move down to right subtree of tree1 and repeat 3

Below is the modified preorder traversal of tree which does the trick for us.

Subtree of binary search tree : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
#define true 1
#define false 0
#define MAX(a,b)  (a < b ? b : a)
 
 int isIdenticalBST(Node *node1, Node *node2){
	if(!node1 && !node2) return true;
 
	if(!node1 || !node2) return false;
 
	return (node1->value==node2->value 
			&& isIdenticalBST(node1->left, node2->left)
			&& isIdenticalBST(node1->right, node2->right));
}
 
int isSubtree(Node *node1, Node * node2){
	if(!node1) return false;
	if(!node2) return true;
 
	if (isIdenticalBST(node1, node2)) return true;
 
	return isSubtree(node1->left, node2) 
               || isSubtree(node1->right, node2);
}
 
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
 
	return newNode;
}
Node *addNode(Node *node, int value){
	if(!node){
		return createNode(value);
	}
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value);
 
	return node;
}
 
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
 
	Node *root2 = NULL;
	root2 = addNode(root2, 40);
	root2 = addNode(root2, 35);
	root2 = addNode(root2, 39);
	root2 = addNode(root2, 45);
	int height = 0;
	printf( "Is tree subtree : %s", 
		isSubtree( root, root2 ) ? "Yes" : "No" );
 
	return 0;
}

Complexity of algorithm to find if a tree is subtree of binary search tree is O(mn) where m and n are nodes in smaller and bigger tree.

There is another way, it can be done in O(n) complexity where inorder and preorder traversals of two trees are stored in arrays. Check if inorder traversal of smaller tree is subarray of inorder traversal of larger tree and check if preorder traversal of smaller tree is subarray of preorder traversal bigger tree.

If above conditions are true, tree is subtree of larger tree else not. However, we require O(n) extra space.

Why we need to compare two traversals and not only one? Because at least two traversals of tree are required to uniquely define a binary tree.

Please share if there is something wrong or missing. We would love to hear from you. If you want to contribute to website, please contact us and earn money.