BST Inorder Successor in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the inorder successor of a node in a Binary Search Tree (BST)?

The inorder successor of a node in a BST is the node with the smallest key greater than the given node's key. It is the next node visited in an inorder traversal.

beginner

How do you find the inorder successor if the node has a right child?

If the node has a right child, the inorder successor is the leftmost node in the node's right subtree.

intermediate

How do you find the inorder successor if the node has no right child?

If the node has no right child, the inorder successor is one of its ancestors. Specifically, it is the lowest ancestor of the node whose left child is also an ancestor of the node.

beginner

What is the inorder successor of the maximum node in a BST?

The maximum node in a BST has no inorder successor because there is no node with a greater key.

intermediate

Explain the role of parent pointers in finding the inorder successor.

Parent pointers allow moving up the tree to find the inorder successor when the node has no right child. Without parent pointers, you need to start from the root to find the successor.

What is the inorder successor of a node with a right subtree?

A The node itself

B The leftmost node in the right subtree

C The parent node

D The rightmost node in the left subtree

The inorder successor is the smallest node greater than the current node, which is the leftmost node in its right subtree.

If a node has no right child, how do you find its inorder successor?

A Find the rightmost node in the left subtree

B The inorder successor is the root

C The node has no inorder successor

D Find the lowest ancestor whose left child is also an ancestor of the node

When no right child exists, the successor is the lowest ancestor where the node lies in the left subtree.

What is the inorder successor of the maximum node in a BST?

A The root node

B The minimum node

C No inorder successor exists

D The parent node

The maximum node has no node with a greater key, so no inorder successor exists.

Why are parent pointers helpful in finding the inorder successor?

A They allow moving up the tree without starting from the root

B They store the successor directly

C They help find the minimum node

D They are not helpful

Parent pointers let you move up ancestors to find the successor without restarting from the root.

In an inorder traversal, what order are nodes visited?

A Left subtree, node, right subtree

B Node, left subtree, right subtree

C Right subtree, node, left subtree

D Node, right subtree, left subtree

Inorder traversal visits nodes in ascending order: left subtree first, then node, then right subtree.

Describe the steps to find the inorder successor of a node in a BST when the node has a right child.

Think about the smallest node greater than the current node.

Explain how to find the inorder successor of a node without a right child in a BST.

Consider the path from the node to the root.