# 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
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?
A
1. 3
2. 4
3. 5 (an empty tree is 0)
6
Q
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?
A
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
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:

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
9
Q

What is a tree (what does it represent)

A

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