tree_flashcards
What is a leaf node in a tree?
A node that has no children
What is a root node in a tree?
The top node in a tree that has no parent
What are siblings in a tree?
Nodes that share the same parent node
What are cousins in a tree?
Nodes that have parents who are siblings
What is the level/depth of a node?
The number of edges from the root to that node
`What is the height of a tree?
The number of edges in the longest path from root to any leaf
What is the degree of a node?
The number of children that node has
What is an edge in a tree?
The connection between two nodes
What is inorder traversal?
Visit left subtree, then root, then right subtree (LNR)
What is preorder traversal?
Visit root, then left subtree, then right subtree (NLR)
What is postorder traversal?
Visit left subtree, then right subtree, then root (LRN)
What is level-order traversal?
Visit nodes level by level, left to right
What makes a valid Binary Search Tree (BST)?
For every node: all values in left subtree are less than node’s value and all values in right subtree are greater
What makes a tree balanced?
the heights of left and right subtrees of any node differ by at most one (-1, 0, 1)
What is an AVL tree?
A self-balancing BST where heights of left and right subtrees differ by at most one for all nodes
What is the balance factor in an AVL tree?
The difference between the height of the right subtree and the left subtree (left subtree - right subtree)
What is the time complexity for searching in a balanced BST?
O(log n)
What is the time complexity for searching in an unbalanced BST (worst case)?
O(n)
What is the primary advantage of AVL trees?
Guaranteed O(log n) performance for all operations (search, delete, add)
What is the main disadvantage of AVL trees?
Extra memory for balance factors and computational overhead for rebalancing after modifications
What is a rotation in AVL trees?
A balancing operation that changes the structure of the tree while maintaining BST properties
What is a perfect binary tree?
A binary tree where all interior nodes have two children and all leaves are at the same level
What is a complete binary tree?
A binary tree where all levels except possibly the last are completely filled
What is a full binary tree?
A binary tree where every node has either 0 or 2 children (no nodes have only one child)
Why do we care about the shape of a tree?
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.
