Intro DS: Trees & Binary Trees

Trees

The following video gives a good introduction to trees in computer science:



Reflection Questions on Trees:

  1. What do the following terms mean, with respect to a Tree: root, node, edges, children, parent, siblings, leaves, ancestors, descendents, sub-trees?

  2. How is a tree data structure fundamentally different from the other data structures you have already studied (Array, Linked List, ArrayList, Stack and Queue)? Describe the differences with respect to:
    • Linearity and the concept of the next element and previous element;
    • The ordering of the Nodes;
    • The number of beginning nodes and ending nodes;
    • Speed of access  (time complexity) to reach a particular node;
    • Programming complexity to build the structure.

  3. What are the advantages of using a Tree data structure to represent heirarchical data?

  4. Why do we refer to a Tree as a recursive data structure?

  5. If we do not draw arrows on the edges of a tree, is the tree undirected?

  6. What is the difference between nil and null pointers? (Hint: for our purposes in the course, there is no difference)

  7. How do we calculate the depth of a node?

  8. How do we calculate the height of a tree?*

  9. How do we calculate the level of a node?

  10. If a tree only has one node, the root, what is the height of such a tree?

  11. If a tree has zero nodes, what is it called? What is the height of such a tree?

  12. What does it mean for a tree to be balanced? 

* NOTE: With respect to the height of a tree, there are two different definitions used by computer scientits. Some computer scientists consider a tree with just a root node to be of height 1 and, therefore, a tree with zero nodes (an empty tree) to be of height zero.
But a more common definition (the one we will use in this course), is that a tree with just the root node has a height of zero. This necessarily means that an empty tree would be defined to be of height -1. 

Binary Trees


The following video discusses binary trees:




Reflection Questions on Binary Trees






  1. What makes a tree a binary tree? Is the figure, above, a binary tree?

  2. What is the difference between a complete binary tree and a perfect binary tree? Is the figure, above, a complete or perfect binary tree? Is it both?

  3. How can we calcluate the maximum number of nodes at a given level of a binary tree? What is the maximum number of nodes we can have in Level 5 of a binary tree?

  4. If a perfect binary tree has height h, what is the formula (in terms of h) for calculating how many nodes it has?

  5. Given a perfect binary tree with n nodes, what is the formula (in terms of n) to calculate its height? (Hint: take the previous formula and solve for h)

  6. Given a binary tree with n nodes, what is the maximum height of an unbalanced tree?

  7. Can we store a binary tree in an array? What restrictions must be placed on the tree to permit this?

  8. What are the properties of a Binary Search Tree (BST)? Is the figure, above, a Binary Search Tree?