Please enable JavaScript.

Coggle requires JavaScript to display documents.

Trees - Coggle Diagram

- - - - Length of the unique path from the root to v
    - - Length of the longest unique path from the node to a leaf
    - - Complete m-ary tree: levels filled from top to bottom, left to right
      - Full m-ary tree: exactly m children
      - m-ary tree, where m = 2: binary tree
  - - - A binary tree can be defined as an ordered tree in which every vertex has no more than two children and each child is designtaed as either a left child or a right child of its parent. A binary tree may also be empty
      - Traversals
        
        All three traversals visit nodes of a binary tree recursively by visiting the tree’s root and its left and right subtrees
        
        Preorder Traversal
        
        The root is visited before the left and right subtrees
        are visited (in that order)
        
        Inorder Traversal
        
        The root is visited after visiting its left subtree but
        before visiting the right subtree
        
        Postorder traversal
        
        The root is visited after visiting the left and right
        subtrees (in that order)
    - - Complexity
        
        Space Complexity
        
        Worst Case
        
        O(n)
        
        Time Complexity
        
        Average Case
        
        Acess: Θ(log(n))
        
        Search: Θ(log(n))
        
        Insertion: Θ(log(n))
        
        Deletion: Θ(log(n))
        
        Worst Case
        
        Acess: O(n)
        
        Search: O(n)
        
        Insertion: O(n)
        
        Deletion: O(n)
      - A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree
      - Height
        
        It can be computed as the maximum of the heights of the root’s left and right subtrees plus 1 (We have to add 1 to account for the exttra level of the root). Is also convenient to define the height of the empty tree as -1