data structures using tree tree tca similar binary trees two binary trees and tcare said to be similar if both these trees have the same structure figure shows two similar binary trees copies two binary trees and tcare said to be copies if they have similar structure and if they have same content at the corresponding nodes figure shows that tcis copy of figure similar binary trees tree tree tca figure edge it is the line connecting node to any of its successors binary tree of nodes has exactly edges because every node except the root node is connected to its parent via an edge path sequence of consecutive edges for examplein fig the path from the root node to the node is given as and leaf node node that has no children is called leaf node or terminal node the leaf nodes in the tree are and tcis copy of depth 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 height of tree it is the total number of nodes on the path from the root node to the deepest node in the tree tree with only root node has height of binary tree of height has at least nodes and at most nodes this is because every level will have at least one node and can have at most nodes soif every level has two nodes then tree with height will have at the most nodes as at level there is only one element called the root the height of binary tree with nodes is at least log ( + and at most in-degree/out-degree of node it is the number of edges arriving at 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 binary trees are commonly used to implement binary search treesexpression treestournament treesand binary heaps complete binary trees complete binary tree is binary tree that satisfies two properties firstin complete binary treeevery levelexcept possibly the lastis completely filled secondall nodes appear as far left as possible in complete binary tree tnthere are exactly nodes and level of can have at most nodes figure shows complete binary tree note that in fig level has nodelevel has nodeslevel has nodeslevel has nodes which is less than the maximum of nodes in fig tree has exactly nodes they have been purposely labelled from to so that it is easy for the reader to find the parent nodethe right child nodeand the left child node of the given node the formula can be given as--if is parent nodethen its left child can be calculated as and its right child can be calculated as for examplethe children of the node are ( and ( similarlythe parent of the node can be calculated as / given the node its parent can be calculated as / the height of tree tn having exactly nodes is given as figure complete binary tree hn log (