trees learning objective so farwe have discussed linear data structures such as arraysstringsstacksand queues in this we will learn about non-linear data structure called tree tree is structure which is mainly used to store data that is hierarchical in nature in this we will first discuss general trees and then binary trees these binary trees are used to form binary search trees and heaps they are widely used to manipulate arithmetic expressionsconstruct symbol tablesand for syntax analysis introduction tree is recursively defined as set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non-empty sets each of which is sub-tree of the root figure shows tree where node is the root nodenodes bcand are children of the root node and form sub-trees of the tree rooted at node basic terminology root node the root node is the topmost node in the tree if nullthen it means the tree is empty sub-trees if the root node is not nullthen the trees and are called the sub-trees of leaf node node that has no children is called the leaf node or the terminal node path sequence of consecutive edges is called path for examplein fig the path from the root node to node is given asadand ancestor node an ancestor of node is any predecessor node on the path from root to that node the root node does not have any ancestors in the tree given in fig nodes acand are the ancestors of node