Please enable JavaScript.

Coggle requires JavaScript to display documents.

M7 (Since the definition itself divides a binary tree into two smaller…

- - - - if T = ∅ return −1
        else return max{Height(Tlef t ), Height(Tright)} + 1
        
        recurrence for the number of nodes visited
        A(n(T )) = A(n(Tlef t)) + A(n(Tright)) + 1 for n(T ) > 0,
        A(0) = 0.
  - - - They differ only by the timing of the root’s visit:
        In the preorder traversal, the root is visited before the left and right subtrees
        are visited (in that order).
        In the inorder traversal, the root is visited after visiting its left subtree but
        before visiting the right subtree.
        In the postorder traversal, the root is visited after visiting the left and right
        subtrees (in that order).
        
        Their pseudocodes are quite straightforward.
- - - - Rooted Trees Another very important property of trees is the fact that for every
        two vertices in a tree, there always exists exactly one simple path from one of these
        vertices to the other. This property makes it possible to select an arbitrary vertex
        in a free tree and consider it as the root of the so-called rooted tree.
        
        A rooted tree
        is usually depicted by placing its root on the top (level 0 of the tree), the vertices
        adjacent to the root below it (level 1), the vertices two edges apart from the root
        still below (level 2), and so on
- - - - Fortunately, the
        average-case efficiency turns out to be in O(log n).
        
        Fortunately, the
        average-case efficiency turns out to be in O(log n).
        
        Since insertion of a new key into a binary search
        tree is almost identical to that of searching there, it also exemplifies the variablesize-
        decrease technique and has the same efficiency characteristics as the search
        operation.