Friday, April 17, 2015

if binary tree is a subtree of other

is-subtree(node1, node2):
    if node1 == null:
    if node2 == null:
        return true
    return is-subtree-recursive(node1, node2)

is-subtree-recursive(node1, node2):
    if node1 == null:
        return false
    if is-equal(node1, node2):
        return true
    return is-subtree-recursive(node1.left, node2)
        || is-subtree-recursive(node1.right, node2)

is-equal(node1, node2):
    if node1 == null && node2 == null:
        return true
    if node1 == null || node2 == null:
        return false
    return node1.value == node2.value
        && is-equal(node1.left, node2.left)
        && is-equal(node1.right, node2.right)

[Hat tip to ctci]

No comments:

Post a Comment