How to prove #(leaves) equals #(nodes) + 1 method?

  • 0

    Intuitively I use stack to solve this problem. Browsing the discussions makes me realize I can leverage this binary tree's property. However, how to prove this method work?
    We know if the traversal is a valid binary tree's preorder traversal, then the number of leaves equals the number of nodes plus one. What's the mathematical proof that the later condition leads to the former statement?

  • 2

    Think of it recursively.

    Base case:
    If you have one node in a binary tree, it has 1 node and 2 leaves.

    Recursive case:
    for each new node you add to the binary tree, your new node replaces an old leave and add two new leaves, thus gives us 1 new node and 1 new leave.

    That extra 1 leave comes from the base case.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.