Binary Search Trees

Question 1

What are the common tree features?

Answer 1

• Root: Starting-point node of the data structure
• Leaf: a node with no children
• Branch: (or “edge”) a connection between two nodes
• Parent: is connected directly to it’s child(ren) below it
  
  • children with the same parents are siblings

Question 2

In this example, what are descendants and ancestors?

Answer 2

Question 3

What is an interior node?

Answer 3

nodes that have at least one child

Question 4

What is in and out degree?

what is the in-degree of root?

what is the out-degree of leaves?

Answer 4

• in-degree of a node is the number of edges coming in to the node
• out-degree of a node is the number of edges going out of the node

root is always in-degree 0

leaves is always out-degree 0

Question 5

1. What is lenghth of the path from 4-3?
2. What is the heigh of 11?
3. What is the height of the tree?

Answer 5

1. 3
2. 4
3. 5 (an empty tree is 0)

Question 6

1. what is the definition of a recursive tree?
2. can a leaf be conisdered a tree?
3. can a null pointer be considered a tree?

Answer 6

1. A tree is either empty or consists of a root with zero or more tree children
2. Yes, it’s a tree with just a root
3. yes, it’s an empty tree

Question 7

What are the tree operations?

Answer 7

• search(d): Is the data d in the tree?
• insert(d): Insert d into the tree (adds a new node)
• delete(d): Delete data d from the tree (deletes a node)
• empty(): returns true if the tree is empty
• traverse(): Examine or perform some operation on all nodes in the tree systematically

Question 8

What is a binary tree and what are it’s properties?

Answer 8

A binary tree is a tree in which each node has at most two children (has outdegree <= 2)

Properties:

1. for each node j, the valeues stored in the left child tree o j are all less than the value stored in j, which is less than all values stored in the right child tree of j
2. the min value is found by starting at the root and repeatedly moving to the left child until you reach a leaf
3. the max value is found by starting at the root and repeatedly moving to the right child until you reach a leaf

Question 9

What is a tree (what does it represent)

Answer 9

A tree represents a hierarchical relationship among data (such as a file system)