Introduction
Trees are a type of non-linear data structure. Data structures such as arrays and linked lists are linear data structures - because they store data in a sequential order. A non-linear data structure, like tree can be visualised as a hierarchical family tree with the grand parents at the top, followed by parents and their children. This kind of data structure is called as tree, analogous to an actual tree with one root, several branches and leaves. The topmost element is called a root (so you can imagine an upside down tree for reference), and all trees have a single root element. Tree elements are called nodes, which carry data stored at that particular node and the address of its children. A root can have several children. The last child of any branch is called a leaf.
Binary Trees
There are several kinds of trees. The most widely used among them are binary trees. Binary trees are like ordinary trees with the constraint that each node can have at the maximum only two children that is, a node can have 0, 1 or 2 children, not more than that. Each node is a subtree, as tree is a recursive function - "A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree. Here's an example of a binary tree :
As you can see in the figure above, each node has at max 2 children - the left child and the right child. The structure of a binary tree can be defined as :
Terminologies related to a tree
Root : The topmost node in a tree
Parent : The predecessor of a node (which has the address of this node)
Child : The successor of a node (whose address the node contains)
Leaf : A node with no (or NULL) children
Internal node : A node with at least 1 child
External node : The leaf nodes, i.e., nodes with no children
Path : A branch of a tree, i.e., a sequence of linked nodes (note : siblings are not linked to each other, only a parent is linked to a child)
Edge : Connecting links between nodes
Ancestor : Just like in a family, an ancestor of a node is another node which came before it in its own path/branch.
Descendant : A descendant of a node is another node which comes after it in its own branch/path.
Height : The number of links from the root to the deepest leaf
Depth : The number of edges from node to root
Level : Level of a node is depth + 1
Related Links :
