Intro DS: Trees & Binary Trees
TreesThe following video gives a good introduction to trees in computer science:
Reflection Questions on Trees:
- What do the following terms mean, with respect to a Tree: root, node, edges, children, parent, siblings, leaves, ancestors, descendents, sub-trees?
- 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.
* 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.
The following video discusses binary trees:
Reflection Questions on Binary Trees
- What makes a tree a binary tree? Is the figure, above, a binary tree?
- 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?
- 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?
- If a perfect binary tree has height h, what is the formula (in terms of h) for calculating how many nodes it has?
- 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)
- Given a binary tree with n nodes, what is the maximum height of an unbalanced tree?
- Can we store a binary tree in an array? What restrictions must be placed on the tree to permit this?
- What are the properties of a Binary Search Tree (BST)? Is the figure, above, a Binary Search Tree?