trees are often used for implementing other types of data structures like hash tablessetsand maps self-balancing treered-black tree is used in kernel schedulingto preempt massively multiprocessor computer operating system use (we will study red-black trees in next another variation of treeb-trees are prominently used to store tree structures on disc they are used to index large number of records (we will study -trees in -trees are also used for secondary indexes in databaseswhere the index facilitates select operation to answer some range criteria trees are an important data structure used for compiler construction trees are also used in database design trees are used in file system directories trees are also widely used for information storage and retrieval in symbol tables points to remember tree is data structure which is mainly used to store hierarchical data tree is recursively defined as collection of one or more nodes where one node is designated as the root of the tree and the remaining nodes can be partitioned into non-empty sets each of which is sub-tree of the root in binary treeevery node has zerooneor at the most two successors node that has no successors is called leaf node or terminal node every node other than the root node has parent the degree of node is equal to the number of children that node has the degree of leaf node is zero all nodes that are at the same level and share the same parent are called siblings two binary trees having similar structure are said to be copies if they have the same content at the corresponding nodes binary tree of nodes has exactly edges the depth of node is given as the length of the path from the root to the node the depth of the root node is zero binary tree of height has at least nodes and at most nodes the height of binary tree with nodes is at least log ( + and at most in-degree of node is the number of edges arriving at that node the root node is the only node that has an in-degree equal to zero similarlyout-degree of node is the number of edges leaving that node in complete binary treeevery level (except possibly the lastis completely filled and nodes appear as far left as possibly binary tree is said to be an extended binary tree (or -treeif each node in the tree has either no children or exactly two children pre-order traversal is also called as depth-first traversal it is also known as the nlr traversal algorithm (nodeleft-rightand is used to extract prefix notation from an expression tree in-order algorithm is known as the lnr traversal algorithm (left-node-rightsimilarlypost-order algorithm is known as the lrn traversal algorithm (left-right-nodethe huffman coding algorithm uses variablelength code table to encode source character where the variable-length code table is derived on the basis of the estimated probability of occurrence of the source character exercises review questions explain the concept of tree discuss its applications what are the two ways of representing binary trees in the memorywhich one do you prefer and why list all possible non-similar binary trees having four nodes draw the binary expression tree that represents the following postfix expressionab+ *