BST Inorder Successor in DSA Go - 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.

intermediate

What is the time complexity of finding the inorder successor in a BST?

The time complexity is O(h), where h is the height of the BST, because you may need to traverse up or down the tree along the height.

beginner

In Go, what data structure is typically used to represent a BST node for inorder successor problems?

A struct with fields for the node's value, left child pointer, right child pointer, and optionally a parent pointer to help find ancestors.

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

A The root node

B The node itself

C The minimum node in the BST

D Nil (no successor)

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

If a node has a right child, where do you look to find its inorder successor?

A Right child's leftmost descendant

B Right child's right subtree

C Left child's rightmost descendant

D Parent node

The inorder successor is the leftmost node in the right subtree.

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

A Go to the left child

B Go up to the lowest ancestor whose left child is also an ancestor of the node

C Go to the right child

D There is no successor

You move up the tree to find the lowest ancestor where the node is in the left subtree.

What is the worst-case time complexity to find the inorder successor in a BST?

A O(1)

B O(log n)

C O(h)

D O(n)

The time depends on the height h of the BST, which can be up to O(n) in worst case but generally O(log n).

Which of these is NOT needed to find the inorder successor of a node in a BST?

A Root of the BST

B Node's parent pointer

C Node's right child

D Node's left child

You do not need the root to find the inorder successor if you have the node and its parent pointers.

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

Think about the next bigger value in the tree.

Describe the steps to find the inorder successor when the node has no right child.

Consider the path from node to root.