Skip to main content

Induction Proof

Claim:

Given a binary tree, the following preorder function prints every node in the tree.​

def preorder(node: Node) -> None:
    if node is None: return
    print(node.val)
    preroder(node.left)
    preorder(node.right)

Proof

  • N is defined to be some number of nodes in a tree greater than 1.

Base case​

  • 0 node: nothing is printed and the function terminates.
  • 1 node: The node is printed and its null left and null right print nothing and the function terminates.

Inductive step​

  • Inductive assumption: for every tree with equal to or less than N nodes, every node is printed and function terminates.
  • Let a tree with N + 1 elements be given.

(1) The root node is printed with print(node.val).

  • There are at max 2 sub-trees. The left subtree has at max N nodes and the right subtree has at max N nodes.

(2) preorder(root.left) is printed according to the inductive assumption, since there are at max N nodes on the left subtree.

(3) preorder(root.right) is printed according to the inductive assumption, since there are at max N nodes on the right subtree.

Q.E.D.