(Ch. 20) Understanding Binary Trees and Their Operations

binary tree

A nonlinear linked structure where each node may point to up to two child nodes.

root node

The first node in a binary tree, serving as the entry point.

child node

A node that descends from another node in a binary tree.

leaf node

A node with no children.

subtree

A branch of the tree starting from any node and including all its descendants.

binary search trees rule

The left child holds a lesser value; the right child holds a greater value.

IntBinaryTree class

To store and manipulate integers in a binary search tree structure.

TreeNode struct

struct TreeNode { int value; TreeNode left, right; };

insertNode function

Creates and inserts a new node into the binary search tree.

inorder traversal

Left subtree → Current node → Right subtree.

preorder traversal

Current node → Left subtree → Right subtree.

postorder traversal

Left subtree → Right subtree → Current node.

searchNode(int)

Returns true if a value exists in the tree; otherwise false.

remove(int)

Removes a node with the specified value from the tree.

node with two children deletion

Right subtree is linked to parent; left subtree is attached to the leftmost node of the right subtree. delete the replacement node

makeDeletion()

Reattaches subtrees and deletes the node.

tree template

Generic binary search trees that can store any data type.

binary tree template operators

Operators <, >, and == must be supported.

insertion order effect

It determines the structure and balance of the tree.

destroySubTree() purpose

Deletes all nodes in the tree recursively, used in the destructor.

remove() function internal call

Internally calls deleteNode() to locate and remove the node.

binary tree ascending order print

By using inorder traversal.

What tree results from inserting 10, 5, 15, 2 into a BST?

10 root, 5 left, 15 right, 2 under 5.

What does insert(TreeNode *&node, int val) do?

Inserts into BST by modifying node by reference.

What is base case in any traversal?

if (node == nullptr) return;

What is preorder traversal of 10, 5, 15?

10 5 15

How do you count all nodes?

return 1 + count(left) + count(right)

What does makeDeletion() do?

Handles replacement and cleanup of a node in deletion.

Why use template with BinaryTree?

To store any comparable type (supports <, >, ==).

What happens if T doesn't support < in BinaryTree?

Compilation fails — missing operator.

Why use TreeNode*& in insert/delete?

Allows modifying actual pointer passed from parent.

What must destructor of BinaryTree do?

Recursively delete all nodes (postorder).

Q: What happens when you delete a leaf node from a binary tree?

A: Simply remove the node and set its parent's pointer to nullptr.

Q: What happens when you delete a node with one child?

A: Replace the node with its only child by linking the parent to the child.

Q: What is the inorder successor in a binary search tree?

A: The smallest value node in the right subtree of the node being deleted - the next node in inorder traversal.

Q: What is the replacement called when using the largest node in the left subtree?

A: Inorder predecessor.

Q: What is the inorder predecessor in a binary search tree?

A: The largest value in the left subtree — the previous node in inorder traversal.

Q: What is outdegree in a directed graph?

A: The number of edges leaving a node.

Q: What is indegree in a directed graph?

A: The number of edges coming into a node.

Q: How can you find outdegree from an adjacency list?

A: Count how many nodes are listed in that vertex’s list.

Q: How can you find indegree from an adjacency list?

A: Count how many times the vertex appears in all lists.

Q: What happens when you delete a node with two children?

A: Replace it with its inorder successor (smallest value in right subtree), then delete that successor.