A binary tree is substree of another binary tree

April 21, 2016

Introduction

It is the great experience to review the recursive function through the algorithm called "Is subtree". Depth first search algorithm is very basic one using recursive function call, it is the fast and quick way to write an algorithm and also very popular in the interviews.

Problem statement:
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.

Another solution:
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/

O(n) time, special case handling - for leaf node of tree - append null 

Question and answers:

1. What do you learn through this study? How long does it take you to figure out things? 

Answer: First, it is about the subtree definition: it should be uniquely defined; for any node in the tree, the subtree starting from the node is only one. In other words, the node is the start, and all leaf nodes underneath should all be included.

2. The very good way to think recursively; do not repeat the work, do not do the extra work; only work on root node, since every node can be root node; get in the loop or recursive function. 

3. Let us walk through the code and add some comment: The code link is here. 

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace TreeIsAnotherTreeSubtree
	{
	/// <summary>
	/// code review on June 17, 2017
	/// </summary>
	class Program
	{
	internal class Node{
	public int Data { get; set; }
	public Node Left { get; set; }
	public Node Right { get; set; }
	}
	static void Main(string[] args)
	{
	}
	/// <summary>
	/// Function is designed to see if a tree is a subtree of the other tree.
	/// </summary>
	/// <param name="tree"></param>
	/// <param name="subTree"></param>
	/// <returns></returns>
	public static bool IsSubtree(Node tree, Node subTree)
	{
	/* base cases */
	// Julia: subtree is null, assume that a null is valid subtree.
	if (subTree == null)
	{
	return true;
	}
	// tree is empty, then, return false.
	if (tree == null)
	{
	return false;
	}
	// Now, let us check if subtree and tree are identical; if it is, then return true.
	if (areIdentical(tree, subTree))
	{
	return true;
	}
	// otherwise, continue to check subtree with tree's left and right child, ask same question.
	return IsSubtree(tree.Left, subTree) || IsSubtree(tree.Right, subTree);
	}
	/// <summary>
	/// Two trees are identical - check every node in the tree
	/// </summary>
	/// <param name="node1"></param>
	/// <param name="node2"></param>
	/// <returns></returns>
	private static bool areIdentical(Node node1, Node node2)
	{
	// base case: both trees are null, then true;
	if (node1 == null && node2 == null)
	{
	return true;
	}
	// afterwards, if any one is null, then, return false;
	if (node1 == null || node2 == null)
	{
	return false;
	}
	// check 3 things: first, two nodes are having same value;
	// and then, check both left child;
	// and then, check both right child.
	return (node1.Data == node2.Data &&
	areIdentical(node1.Left, node2.Left) &&
	areIdentical(node1.Right, node2.Right));
	}
	}
	}

view raw TreeIsAnotherTreeSubtree.cs hosted with ❤ by GitHub

Dec. 25, 2016

Read the code review on stackexchange.com.

Algorithm called "is subtree"

http://codereview.stackexchange.com/questions/6774/check-if-a-binary-tree-is-a-subtree-of-another-tree
http://codereview.stackexchange.com/questions/117325/find-if-a-given-tree-is-subtree-of-another-huge-tree

Follow up 

June 17, 2017

Find out leetcode algorithm related algorithm. 

Blog to read:
Need to review KMP algorithm - strstr - O(N) algorithm:

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/