—In computer science, a tree is an abstract model of a hierarchical structure. —A tree consists of nodes with a parent-child relation. —Previous data structures placed data in linear order. —Some data organizations require categorizing data into groups, subgroups. —Trees are a hierarchical data structure of nodes. —Nodes are linked by edges. A parent node references one or more nodes (children nodes) that are “lower” in the tree hierarchy.

If node u has address of node v, then v is the child of u

Root Node

Node without parent is called root node. Except for the root (no parent), every node has exactly one parent (by definition). A tree has only one root node.

Sibling Node

Nodes that are children of the same parent are called sibling.

Internal Nodes

—A node is internal if it has one or more children.

Leaf Node

A node is a leaf if it has no children

Ancestor and Descendant Nodes

—An ancestor of a node is either the node’s parent  or any ancestor of the node’s parent i.e. parent, grandparent, grand-grandparent. —The root is an ancestor of every other node. —Descendant of a node: child, grandchild, grand-grandchild.


—The subtree of T rooted at node v is the tree consisting of all the descendents of v in T (including v)
—tree consisting of a node and its descendants

Depth of a Tree

The depth of a node v in T is the number of ancestors of v, excluding v.
More formally: If v is the root, the depth of v is 0

Height of a Tree

—The height of a tree is the maximum depth of its lowest level leaves. Also called maximum levels of a tree

—Two nodes are adjacent if an edge connects them. —A path is a sequence of nodes in which each node is adjacent to the next one. —Every node in the tree can be reached by following a unique path starting from the root. The length of a path is the number of edges on the path.

—The path from the root, A, to the leaf, I, is denoted as AFI and has a length of 2. —ABD is the path from the root, A, to the leaf, D, and also has a length of 2.

Types of Trees

1. —General tree – a node can have any number of children
2. —Binary tree – a node can have at most two children
Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.