M13: Quiz - Trees & Heaps

Binary Search Tree (BST)

A binary tree where left child < parent < right child for every node\n\n

BST inorder traversal

Visits nodes in sorted (ascending) order\n\n

Inorder traversal order

Left subtree → Node → Right subtree\n\n

Preorder traversal

Node → Left subtree → Right subtree\n\n

Postorder traversal

Left subtree → Right subtree → Node\n\n

Level

order traversal

Binary tree height

Maximum number of edges from root to deepest leaf\n\n

BST height example result

Height of BST built from 12, 24, 23, 48, 47 is 3\n\n

Perfect binary tree

A tree where all internal nodes have 2 children and all leaves are at the same depth\n\n

Complete binary tree

All levels filled except possibly last, filled left to right\n\n

Full binary tree

Every internal node has exactly two children\n\n

Perfect binary tree node formula

N = 2^(h+1)

Perfect binary tree leaves formula

2^h leaves at height h\n\n

Perfect binary tree height 3 leaves

8\n\n

Perfect binary tree height 4 nodes

31\n\n

Internal nodes in full binary tree (height 4)

15\n\n

BST remove node case 3 (left child only)

node.parent.replace_child(node, node.left)\n\n

BST replace_child condition

new_child != None\n\n

BST replace_child purpose

Replaces a child node while maintaining parent links\n\n

BST inorder recursive step

BST_print_in_order(node.left)\n\n

BST height function formula

1 + max(left_height, right_height)\n\n

BST search worst case comparisons

height + 1 comparisons\n\n

BST search height 3 worst case

4 comparisons\n\n

BST delete result example

Removing 4 leaves tree rooted at 6 with children 3 and 8\n\n

BST successor

Smallest node in the right subtree\n\n

BST predecessor

Largest node in the left subtree\n\n

Heap

A complete binary tree that satisfies heap property\n\n

Min

heap property

Max

heap property

Heap root location

The root always contains the highest priority element\n\n

Heap remove operation

Removes root and rebalances tree using heapify\n\n

Heap after removal example

Root becomes 60 after removing 77\n\n

Set behavior in Python

Automatically removes duplicates\n\n

Python set add behavior

Adding same element multiple times does not change size\n\n

Python set length example

Adding A, B, C, a, b, c results in 6 elements\n\n

Union operation (set)

Combines all unique elements from both sets\n\n

Set union method behavior

Adds all elements from both sets into one\n\n

BST validity rule

Left subtree < node < right subtree must always hold\n\n

Valid BST example

Root 6 with left 4 and right 8 is a valid BST\n\n

Invalid BST example

Node values violate ordering rule (e.g., right child smaller than root)\n\n

Node parent in BST delete

Parent pointer is used to reconnect children after deletion\n\n

BST remove node types

Leaf, one child, two children, root case\n\n

BST remove root case

Special handling required when deleting root node\n\n

Tree node relationship

Each node has at most one parent and up to two children\n\n

Binary tree structure

A tree where each node has at most two children\n\n

Heap vs BST difference

Heap is partially ordered, BST is fully ordered\n\n