Binary Tree - Definitions For Rooted Trees

Definitions For Rooted Trees

  • A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree).
  • The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.
  • A leaf node has no children.
  • The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
  • The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.
  • Siblings are nodes that share the same parent node.
  • A node p is an ancestor of a node q if it exists on the path from the root to node q. The node q is then termed as a descendant of p.
  • The size of a node is the number of descendants it has including itself.
  • In-degree of a node is the number of edges arriving at that node.
  • Out-degree of a node is the number of edges leaving that node.
  • The root is the only node in the tree with In-degree = 0.
  • All the leaf nodes have Out-degree = 0.

Read more about this topic:  Binary Tree

Famous quotes containing the words definitions, rooted and/or trees:

    “What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
    —G.C. (Georg Christoph)

    “We must continually remind students in the classroom that expression of different opinions and dissenting ideas affirms the intellectual process. We should forcefully explain that our role is not to teach them to think as we do but rather to teach them, by example, the importance of taking a stance that is rooted in rigorous engagement with the full range of ideas about a topic.”
    —bell hooks (b. 1955)

    “Let us have a good many maples and hickories and scarlet oaks, then, I say. Blaze away! Shall that dirty roll of bunting in the gun-house be all the colors a village can display? A village is not complete, unless it have these trees to mark the season in it. They are important, like the town clock. A village that has them not will not be found to work well. It has a screw loose, an essential part is wanting.”
    —Henry David Thoreau (1817–1862)