Hi guys, today I am going to discuss trees. We are going to discuss basic concepts of tree data structure before we start discussion about binary trees.
Tree:
Tree is a abstract data structure used to stored data in hierarchical order.
In simple words imagine a diagram showing family members of your family showing relationships like parent-children, grandparents. This diagram is in term a ‘tree data structure’. As you can imagine, its difficult to maintain such type of orders in linear data structure (array, linked list etc.) tree data structure is require.
Basic difference between graph and tree is there are no loops or circles in trees, so each element (referred as node) of tree can be accessed by accessing unique path.
Tree is defined as a binary tree, ternary tree …k-ary depending on maximum number of children a parent element can have.
Tree Terminology:
Root: The topmost node of a tree with no parent.
Leaf Node: Nodes of tree with no children.
Path: Sequence of nodes connected with edges.
Length of path: Number of edges connecting nodes between that path.
Height of node: Longest path from node that node to leaves.
Height of tree: Longest path from root and a leaf.
Depth of node: Distance(number of edges) of that node from root. So for ‘root’ depth=0
and height can be considered as maximum depth of all nodes.
Degree of node: Number of direct children of that node.
Considering these tree terminologies one can say:
-In tree each node can have at the most one parent.
-Each node can be traversed from a root node.
-Each node of a tree can be considered a sub-tree. This property of trees is used to implement trees recursively.
Lets discuss about binary trees in next session…