Trees

Trees

1. Strict trees

   • e=i+1
   • 0/2 children each node

2. n-ary trees

   • Capacity of each node is 0-n
   • Strict n-ary
     • Exactly 0 or n children
     • min nodes if height h: nh+1
     • e=(m-1)i+1

3. Binary Tree

   • Array rep
     • If root node is at position p
       • left node at 2p
       • right node at 2p+1
   • Linked list rep

4. Traversal

   • Inorder
     • left->root->right
   • Preorder
     • root->left->right
   • Postorder
     • left->right->root

5. AVL TREES

   • bf= abs(hl-hr)