BST Inorder Successor in DSA Typescript - 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 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 a path.

beginner

In a BST, what does an inorder traversal produce?

An inorder traversal of a BST produces the nodes in ascending sorted order of their keys.

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

A The leftmost node in the right subtree

B The rightmost node in the left subtree

C The parent node

D The root node

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

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

A There is no inorder successor

B Find the rightmost node in the left subtree

C Find the root node

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

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

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

A O(1)

B O(h)

C O(n)

D O(log n)

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

What order does an inorder traversal of a BST produce?

A Descending order

B Random order

C Ascending order

D Preorder

Inorder traversal visits nodes in ascending sorted order in a BST.

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

A No successor exists

B Its parent

C Its right child

D The root node

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

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

Think about the two cases separately: right subtree and ancestors.

Describe the significance of inorder traversal in a BST and how it relates to the inorder successor.

Consider the order nodes appear in inorder traversal.