Friday, April 17, 2015

if binary tree is a subtree of other

bool isSubtree(node1, node2):
    if node1 == null:
        throw
    if node2 == null:
        return true
    return isSubtreeInner(node1, node2)

bool isSubtreeInner(node1, node2):
    if node1 == null:
        return false
    if areEqual(node1, node2):
        return true
    return isSubtreeInner(node1.left, node2)
        || isSubtreeInner(node1.right, node2)

bool areEqual(node1, node2):
    if node1 == null && node2 == null:
        return true
    if node1 == null || node2 == null:
        return false
    return node1.value == node2.value
        && areEqual(node1.left, node2.left)
        && areEqual(node1.right, node2.right)

[Hat tip to ctci]

No comments:

Post a Comment