Single node/leaf of binary tree

Discussion in 'Programmer's Corner' started by Ryan$, Dec 29, 2018.

  1. Ryan$

    Thread Starter Member

    Dec 14, 2018
    178
    2
    Hi, I'm just wondering and not finding the reason why if we have a tree with single node or actually if we have a leaf node of binary tree so it's by default satisfy the min/max heap property .. why?!
    the min/max heap property is claiming that the root of the tree must be greater/smaller from its children respectively to max/min heap. there's no declaration if there's no children then what to decide.. as a result how we actually make a decision that if there's a root/node without children then we are saying its already satisfy min/max heap property?!

    Maybe I'm not understanding the definition of min/max heap property and when its called min/max heap property.

    thanks !
     
    Last edited: Dec 29, 2018
  2. WBahn

    Moderator

    Mar 31, 2012
    24,559
    7,696
    The definition is all you need.

    Let's focus on just a minheap. A minheap requires that, for every node in the tree, the subtree rooted at that node must be no larger than any of the other nodes in that subtree.

    If there are any nodes in the subtree that are smaller than the root node, then the subtree (and the tree as a whole) fails to satisfy the heap criterion.

    If you have a tree with a single node, are there any other nodes in the tree that are smaller than the root node?

    If not, then it satisfies the heap criterion.
     
    Ryan$ likes this.
  3. Ryan$

    Thread Starter Member

    Dec 14, 2018
    178
    2
    I appreciate you very much, and let me explain what I was know about the definition of min heap: to satisfy min heap property must occur: the children of the root is smaller than the root itself(parents) , how could I conclude from this the leaf is satisfy in trivially the min heap property?! here I'm stuck in .. because I realized the definition of min heap in wrong way I stuck in!

    thanks in advance, convinced me very much!
     
  4. WBahn

    Moderator

    Mar 31, 2012
    24,559
    7,696
    You've got two problems here. A minheap gets it's name because the minimum value of all the data stored in the structure is at the root node. What you are attempting to describe is a max heap. Second, even adjusting for this mistake, this is not the definition and this definition will lead to problems. The definition is that the root must be no larger than any of its children, or equivalently, no child can be smaller than its parent. Your definition, that the root must be smaller, means that it is impossible to put two data values that are equal into a heap because you will have someplace were a parent is equal to its child, which would violate a definition that said it had to be smaller.

    If I was accepting applications for some dangerous assignment and had a rule that only people that do not have children under the age of ten will be accepted, could someone that doesn't have any children apply without violating the rule? Of course! Someone that doesn't have ANY children trivially satisfies the requirement of not having children under the age of ten.

    It's the same thing here. If the requirement for a minheap is that no node has any children that have a smaller value than the parent, then a node that has no children at all trivially satisfies that requirement because it is IMPOSSIBLE for a node with no children to have a child that has a smaller value than it does!
     
Loading...