Skip to content

Problems

Terminology

  1. What is a root node?
  2. What is the difference between depth, height, and level?
  3. What is a:
    • Ancestor
    • Sibiling
    • Child
    • Parent
  4. What are internal nodes? Leaf nodes?

Traversals

  1. What distinguishes each traversal type (preorder, inorder, postorder) from each other?
  2. Write the order in which the nodes are visited when performing the following traversals:
    • Preorder
    • Inorder
    • Postorder

Tree Types

  1. Is the tree above full, complete, or perfect?
  2. If needed, how would you modify the tree so it will become only:
    • Full
    • Complete
    • Perfect

Tree Type Definitions

Type Definition
Full Every node contains 0 or 2 children
Complete All levels, except possibly the last level, are completely full and all nodes in the last level are as far left as possible
Perfect All internal nodes have 2 children and all leaf nodes are at the same level

Comments