Tree data structure–Explained

“ Tree is hierarchical chart about data which can simplify management of data based on the hierarchy they belong to”

Metaphor

   Tree simply came from a empire’s hierarchical chart. At the top, you will have the King, below him you will have Ministers, Below Ministers, you will have Warrior head, Below Warrior heads, you will have many warriors. This hierarchy is created to simplify the big task of ruling and defending the country.

Concept

  Tree, when considered in a computer science sense, is a part of a graph which is acyclic. There is no possibility of cycles in a tree. It always grows in one direction. Following are the terminologies in a tree:

• Root node – the top node of the tree which doesn’t have parent. If some other node in the tree becomes parent of a tree, it becomes cyclic which breaks the basic property of a tree.
• Ancestor node – parent of a child node. It can be any parent above the tree. Note that all nodes in a tree can have only at most one parent (0 or 1) and 0 parent is only for root.
• Leaf nodes – Nodes that don’t have any children. These are also called as terminal nodes
• height of the tree – as explained in heap data structure. The height is calculated by the number of levels traversed from the root to leaves. If there is only root in a tree, then its height is 0.
• depth of the tree – its reverse of the height. From the leaf nodes to root.

Important concept need to be learnt in a tree is: “Every node in a tree can become root of some subtree”.

Tree - an Introduction

Important points

• Tree is called an ordered tree, if swapping the left and right child of the root of the tree doesn’t look different which is possible only if every node has atleast two childrens except leafs
• There are various use cases of a tree like expression tree, decision tree as explained above in the video.
• There are many interesting problems in a tree, like converting tree to list which will be seen in coming sessions