# Intro DS: Trees & Binary Trees

# Trees

The 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.
- What are the advantages of using a Tree data structure to represent heirarchical data?
- Why do we refer to a Tree as a recursive data structure?
- If we do not draw arrows on the edges of a tree, is the tree undirected?
- What is the difference between nil and null pointers? (Hint: for our purposes in the course, there is no difference)
- How do we calculate the depth/level of a node?
- How do we calculate the height of a tree?
***** - If a tree only has one node, the root, what is the height of such a tree?
- If a tree has zero nodes, what is it called? What is the height of such a tree?
- 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

- 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?