Learning Made Easy

Definition: A  binary tree       T  is a finite set of  nodes    with the following properties: Either the set is empty,  ; or The set consists of a root,  r , and exactly two distinct binary trees   and  ,  . The tree   is called the  left subtree    of  T , and the tree   is called the  right subtree    of  T . They are considered as Ordered subtrees. Level i has   2 i    nodes. In a tree of height h, Leaves are level at h. No of leave are    2 h. No of internal nodes  2 h      -1. No of internal nodes = no of leaves -1 Total no of nodes =  2 h+1   -1 =n In a tree on n nodes  No of leaves is (n+1)/2 height =    Log 2 (n+1)/2 Tree Traversal PostOrder Traversal PreOrder  Traversal InOrder  Traversal PostOrder Traversal :   In post order tree walks process each node after processing its children. PreOrder traversal :   In preorder tree walk processes each  node before processing its children. Inorder Traversal :  Bes

Running time of an algorithm, order of growth.  Worst case.   Running time of an algorithm  increases with the size of the input in the limit as the size of the input increases without bound. Big-theta notation (a=b) g(n) is an asymptotically   tight bound of f(n). Asymptotically non negative/positive. If g(n) is asymptotically negative then theta(g(n)) = empty.  Example 1/2n2 - 3n= theta(n2). Big O-notation (a<=b) Asymptotic upper bound Not tight bound  Theta is stronger than O O notation describe upper bound on every input. We also have amortized analysis.[An amortized analysis is any strategy for analyzing a sequence of perations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive] ] Example The running time is O(n2) means there is a function f(n) that is O(n2) such that for any value of n, no matter what particular input of size n is chosen, the running time of t