Vocab

Question 1

Preorder (Depth-first)

Answer 1

visit a node and then visit the subtrees rooted at each of its children recursively. a.k.a. Depth First traversal.

Question 2

Postorder

Answer 2

recursively visit the subtrees rooted at each child of a node and then visit the node.

Question 3

Breadth - first

Answer 3

visit all nodes at depth d before visiting nodes at depth d + 1.

Question 4

Inorder

Answer 4

Definition: limited to binary tree - recursively visit left child, root, right child

Question 5

Binary Tree

Answer 5

An ordered tree wherein every node has at most 2 children, so either child is either left or right

Question 6

Binary Search Tree

Answer 6

Each node stores a key-value pair. For a given parent, the left child (and the entirety of its subtree) is logically less, and the right child (and the entirety of its subtree) is logically more.

Question 7

Trie

Answer 7

Tree nodes consist of an array of R == alphabet size slots, and a value. Mid-key node will hold link to next node in appropriate alphabet slot, and a null value, final key node will not hold no link, and the corresponding value.

Question 8

Heap

Answer 8

Complete binary tree wherein the key of every node is greater than or equal to the key of its children (Heap-Order Property)

Question 9

2-3 Tree

Answer 9

Tree consisting of 2-nodes (one key, left-link and right-link), and 3-nodes (two keys, left-link, middle-link, right-link).

Question 10

Red-Black Tree

Answer 10

Definition: Binary search tree implementation, strictly consisting of 2-nodes, that conceptually mirrors 2-3 trees (red links represent horizontal, as opposed to vertical links; ie 2 red-linked 2-nodes = 3-node). Red links must lean to the left, can’t have consecutive red links.
Features/Advantages: Insertion guarantees perfect black balance, and with it near O(logn) search. Nearly as effective as 2-3 Tree, much easier to implement.

Question 11

B-Tree

Answer 11

Tree wherein every entry e with key k in an internal node has a link to a child node which is the root of a subtree wherein all keys >= k and < the next entry’s key in the same node as e

Question 12

Root

Answer 12

First node in a tree, no parent node, only children.

Question 13

Acyclic

Answer 13

There is exactly one path connecting any two nodes in a tree

Question 14

Path

Answer 14

A sequence of nodes such that any two consecutive nodes in the sequence from an edge

Question 15

Ancestor

Answer 15

A node reachable by repeatedly proceeding from child to parent

Question 16

Descendent

Answer 16

A node reachable by repeatedly proceeding from parent to child

Question 17

Depth

Answer 17

The number of nodes on the path from the node to the root, including the node itself

Question 18

Height

Answer 18

Height of node V is: if V is a leaf, height == 0, else height = maximum height of its children + 1

Question 19

Internal

Answer 19

A node with at least one child

Question 20

Leaf/external

Answer 20

A node with no children

Question 21

Edge

Answer 21

A pair of nodes, U, V, such that one is a the parent of the other

Question 22

Ordered

Answer 22

A tree is ordered if there is a meaningful linear order among the children of every node

Question 23

Isomorphic

Answer 23

Two ordered trees T’ and T’’ are Isomorphic if the following recursive definition is true: Both have no children OR the roots of T’ and T’’ have the same number of children/subtrees (k), and for i = 0,…,k the ith such subtree of T’ has the same number of child subtrees as the ith such subtree of T’’

Question 24

Proper binary tree

Answer 24

Every node has either 0 or 2 children

Question 25

Complete Binary Tree

Answer 25

Every level, except the last, must be completely filled and all nodes are as far left as possible

Question 26

Trie node

Answer 26

node consisting of an array of links corresponding to alphabet of key set, value

Question 27

2 - Node

Answer 27

Node with one key, two child links (left,right)

Question 28

3 - Node

Answer 28

Node with two keys, three child links (left, middle, right)

Question 29

4 - Node

Answer 29

Node with three keys, four child links(Left, left-middle, right-middle, right). Only temporary in 2-3 Tree; meant to be converted into 3, 2 Nodes

Question 30

Rotation

Answer 30

Step to balance left-leaning Red-Black Tree with right -leaning red link

Question 31

Color flip

Answer 31

Step to balance left-leaning Red-Black Tree with two red links stemming from a single parent.

Question 32

Perfect Balance

Answer 32

condition of a 2-3 tree and Red-Black tree that all null links must be the same distance (have the same depth) to the roots