tree_flashcards

Question 1

What is a leaf node in a tree?

Answer 1

A node that has no children

Question 2

What is a root node in a tree?

Answer 2

The top node in a tree that has no parent

Question 3

What are siblings in a tree?

Answer 3

Nodes that share the same parent node

Question 4

What are cousins in a tree?

Answer 4

Nodes that have parents who are siblings

Question 5

What is the level/depth of a node?

Answer 5

The number of edges from the root to that node

Question 6

`What is the height of a tree?

Answer 6

The number of edges in the longest path from root to any leaf

Question 7

What is the degree of a node?

Answer 7

The number of children that node has

Question 8

What is an edge in a tree?

Answer 8

The connection between two nodes

Question 9

What is inorder traversal?

Answer 9

Visit left subtree, then root, then right subtree (LNR)

Question 10

What is preorder traversal?

Answer 10

Visit root, then left subtree, then right subtree (NLR)

Question 11

What is postorder traversal?

Answer 11

Visit left subtree, then right subtree, then root (LRN)

Question 12

What is level-order traversal?

Answer 12

Visit nodes level by level, left to right

Question 13

What makes a valid Binary Search Tree (BST)?

Answer 13

For every node: all values in left subtree are less than node’s value and all values in right subtree are greater

Question 14

What makes a tree balanced?

Answer 14

the heights of left and right subtrees of any node differ by at most one (-1, 0, 1)

Question 15

What is an AVL tree?

Answer 15

A self-balancing BST where heights of left and right subtrees differ by at most one for all nodes

Question 16

What is the balance factor in an AVL tree?

Answer 16

The difference between the height of the right subtree and the left subtree (left subtree - right subtree)

Question 17

What is the time complexity for searching in a balanced BST?

Answer 17

O(log n)

Question 18

What is the time complexity for searching in an unbalanced BST (worst case)?

Answer 18

O(n)

Question 19

What is the primary advantage of AVL trees?

Answer 19

Guaranteed O(log n) performance for all operations (search, delete, add)

Question 20

What is the main disadvantage of AVL trees?

Answer 20

Extra memory for balance factors and computational overhead for rebalancing after modifications

Question 21

What is a rotation in AVL trees?

Answer 21

A balancing operation that changes the structure of the tree while maintaining BST properties

Question 22

What is a perfect binary tree?

Answer 22

A binary tree where all interior nodes have two children and all leaves are at the same level

Question 23

What is a complete binary tree?

Answer 23

A binary tree where all levels except possibly the last are completely filled

Question 24

What is a full binary tree?

Answer 24

A binary tree where every node has either 0 or 2 children (no nodes have only one child)

Question 25

Why do we care about the shape of a tree?

Answer 25

The shape of a tree directly impacts its performance - a balanced tree ensures O(log n) operations, while an unbalanced/skewed tree can degrade to O(n) performance, essentially becoming as slow as a linked list. This affects all operations including searching, insertion, and deletion.