# Binary Search Trees Flashcards

1

Q

What are the common tree features?

A

- 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

2

Q

In this example, what are descendants and ancestors?

A

3

Q

What is an interior node?

A

nodes that have at least one child

4

Q

What is in and out degree?

what is the in-degree of root?

what is the out-degree of leaves?

A

- 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

5

Q

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

A

- 3
- 4
- 5 (an empty tree is 0)

6

Q

- what is the definition of a recursive tree?
- can a leaf be conisdered a tree?
- can a null pointer be considered a tree?

A

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

7

Q

What are the tree operations?

A

- 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

8

Q

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

A

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

**Properties:**

- 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
- the min value is found by starting at the root and repeatedly moving to the left child until you reach a leaf
- the max value is found by starting at the root and repeatedly moving to the right child until you reach a leaf

9

Q

What is a tree (what does it represent)

A

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