First of all
The problem is also from book <Cracking the coding interview 6th>, at section: IX Interview Questions | 4. Trees and graphs | Question 4.10.
(It's a great book by Gayle Laakmann McDowell, a software engineer from Google, who has interviewed a lot people. )
Algorithms
(A) Search root & match subtree algorithm.
Complexity:
Where:
n
It's the size of large tree.m
It's the size of small tree.k
The occurrences that root of small tree found in larger tree.n2
The count of node search in larger tree, before a subtree is found.
It's between [1, n].m2
The average count matched when a root is found.
For random input, this should be very small.k2
The occurrences of root searched, before a subtree is found.
(B) Traverse both trees to lists respectively, and find sub list.
Complexity:
Time: O(n + m)
Space: O(n + m))
Where:
n
It's the size of large tree.m
It's the size of small tree.
Tips:
- Should use
pre-order traverse, and also need to put null node as a special value to list.
Otherwise different trees might output the same list.
in-order traverse won't work.
Because it might output the same ordered list for different outputs for trees that contains the same elements in different order, even with null node represented with special value.
Compare 2 algorithms:
- A use less memory, thus more scalable for very large input.
- A's speed is unsure, but on average it could still be quicker than B.
- B's algorithm is simpler.
Code
(Following is an implementation in Java containing both algorithms, with test case.)
CheckSubtree.java
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* Given 2 binary tree T1 & T2, they are very large, and T1 is much larger than T2.
* <p>Check whether T2 is a subtree of T1,
*
* @author eric
* @date 2/9/19 1:48 PM
*/
public class CheckSubtree {
/**
* Check whether small tree is subtree of large tree, via searching root & match.
* <p>Return on first match.
*
* @param largeTree large tree,
* @param smallTree small tree,
* @param <T>
* @return true if small tree is subtree of large tree, or small tree is empty,
*/
public static <T extends Comparable> boolean checkViaRootAndMatch(BST<T> largeTree, BST<T> smallTree) {
if (smallTree.size() == 0) return true; // small tree is empty,
BST.BSTNode<T> matchNode = searchAndMatch(largeTree.getRoot(), smallTree); // search root & try match,
return matchNode != null;
}
/**
* Search root, and check whether the subtree there match small tree.
*
* @param largeCurrent subtree of large tree,
* @param smallTree small tree,
* @param <T>
* @return node from large tree that match small tree, or null if not found,
*/
protected static <T extends Comparable> BST.BSTNode<T> searchAndMatch(BST.BSTNode<T> largeCurrent, BST<T> smallTree) {
if (largeCurrent == null) return null; // subtree of large is empty,
T smallRoot = smallTree.getRoot().getValue(); // value of small tree's root,
if (largeCurrent.getValue().compareTo(smallRoot) == 0) { // found root of small tree,
if (match(largeCurrent, smallTree)) return largeCurrent; // also match the whole small tree,
}
BST.BSTNode<T> leftFoundNode = searchAndMatch(largeCurrent.getLeft(), smallTree); // search in left subtree,
if (leftFoundNode != null) return leftFoundNode; // match in left subtree of current,
return searchAndMatch(largeCurrent.getRight(), smallTree); // search in right subtree,
}
/**
* Check whether small tree match at given subtree of large tree.
*
* @param largeCurrent subtree of large tree,
* @param smallTree small tree,
* @param <T>
* @return
*/
protected static <T extends Comparable> boolean match(BST.BSTNode<T> largeCurrent, BST<T> smallTree) {
return match(largeCurrent, smallTree.getRoot());
}
/**
* Check whether subtree of small tree match at given subtree of large tree.
*
* @param largeCurrent subtree of large tree,
* @param smallCurrent subtree of small tree,
* @param <T>
* @return true if subtree of small is subtree of large, or subtree of small is empty,
*/
protected static <T extends Comparable> boolean match(BST.BSTNode<T> largeCurrent, BST.BSTNode<T> smallCurrent) {
if (smallCurrent == null) return true; // smaller reach leaf,
if (largeCurrent == null) return false; // larger is empty, while smaller is not,
if (largeCurrent.getValue().compareTo(smallCurrent.getValue()) != 0)
return false; // current value is different,
if (!match(largeCurrent.getLeft(), smallCurrent.getLeft())) return false; // check whether left subtree match,
return match(largeCurrent.getRight(), smallCurrent.getRight()); // check whether right subtree match,
}
// traverse both tree and generate a list representation, then check whether the small list is sub list of large list,
/**
* Check whether small tree is subtree of large tree, via traverse tree to list & find sublist. Use given null value.
* <p>Return on first match.
*
* @param largeTree
* @param smallTree
* @param <T>
* @return
*/
public static <T extends Comparable> boolean checkViaTraverseAndSublist(BST<T> largeTree, BST<T> smallTree) {
return checkViaTraverseAndSublist(largeTree, smallTree, null);
}
/**
* Check whether small tree is subtree of large tree, via traverse tree to list & find sublist. Use given special value.
* <p>Return on first match.
*
* @param largeTree
* @param smallTree
* @param special special value to represent value of null node in tree,
* @param <T>
* @return
*/
public static <T extends Comparable> boolean checkViaTraverseAndSublist(BST<T> largeTree, BST<T> smallTree, T special) {
if (smallTree.size() == 0) return true; // small tree is empty,
// tree to list,
List<T> largeList = treeToList(largeTree, special);
List<T> smallList = treeToList(smallTree, special);
// System.out.printf("large list: %s\n", largeList);
// System.out.printf("small list: %s\n", smallList);
int idx = Collections.lastIndexOfSubList(largeList, smallList); // find sublist,
return idx >= 0;
}
/**
* Traverse tree and add nodes to list, with pre-order, use special value to represent null node.
*
* @param tree
* @param special special value to represent value of null node in tree,
* @param <T>
* @return
*/
protected static <T extends Comparable> List<T> treeToList(BST<T> tree, T special) {
List<T> list = new LinkedList<>();
treeToList(tree.getRoot(), special, list);
return list;
}
/**
* Traverse subtree and add nodes to list, with pre-order, use special value to represent null node.
*
* @param current
* @param special special value to represent value of null node in tree,
* @param list
* @param <T>
*/
protected static <T extends Comparable> void treeToList(BST.BSTNode<T> current, T special, List<T> list) {
if (current == null) {
list.add(special); // represent null with special value,
return;
}
list.add(current.getValue()); // current,
treeToList(current.getLeft(), special, list); // left subtree,
treeToList(current.getRight(), special, list); // right subtree,
}
}
CheckSubtreeTest.java
(unit test, via TestNG)
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
/**
* CheckSubtree test.
*
* @author eric
* @date 2/9/19 4:18 PM
*/
public class CheckSubtreeTest {
private int n = 10;
// trees, via minimal BST,
private BST<Integer> largeTree; // large tree,
private BST<Integer> smallTree; // small tree, subtree of large tree,
private BST<Integer> smallTree2; // small tree, not subtree of large tree,
private BST<Integer> emptyTree; // empty tree,
@BeforeMethod
public void init() {
// init - large tree,
largeTree = CreateMinimalBST.createRangeNum(0, n);
// init - small tree,
smallTree = CreateMinimalBST.createRangeNum(8, 10);
smallTree2 = CreateMinimalBST.createRangeNum(2, 5);
// init empty BST,
emptyTree = new BST<>();
}
// checkViaRootAndMatch(),
@Test
public void testViaRootAndMatch() {
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(largeTree, smallTree)); // subtree,
Assert.assertFalse(CheckSubtree.checkViaRootAndMatch(largeTree, smallTree2)); // not subtree,
Assert.assertFalse(CheckSubtree.checkViaRootAndMatch(smallTree, largeTree)); // not subtree,
// empty tree,
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(largeTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(smallTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(emptyTree, emptyTree));
}
// checkViaTraverseAndSublist(),
@Test
public void testViaTraverseAndSublist() {
// Integer special = null;
// Integer special = Integer.MAX_VALUE;
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(largeTree, smallTree)); // subtree,
Assert.assertFalse(CheckSubtree.checkViaTraverseAndSublist(largeTree, smallTree2)); // not subtree,
Assert.assertFalse(CheckSubtree.checkViaTraverseAndSublist(smallTree, largeTree)); // not subtree,
// empty tree,
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(largeTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(smallTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(emptyTree, emptyTree));
}
}
All test cases would pass.
Tips:
BST is a simple binary tree impl.BST.BSTNode is BST's node.CreateMinimalBST is a tool that help to build a binary search tree of minimal height.
