BST Inorder Predecessor in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the inorder predecessor in a Binary Search Tree (BST)?

The inorder predecessor of a node in a BST is the node that comes immediately before it in the inorder traversal. It is the largest node smaller than the given node.

beginner

How do you find the inorder predecessor if the node has a left subtree?

If the node has a left subtree, the inorder predecessor is the rightmost (maximum) node in that left subtree.

intermediate

What if the node has no left subtree? How to find its inorder predecessor?

If the node has no left subtree, move up the tree using parent pointers until you find a node which is the right child of its parent. That parent is the inorder predecessor.

intermediate

Why is the inorder predecessor important in BST operations?

The inorder predecessor helps in operations like deletion in BST, where you replace a node with its inorder predecessor to maintain BST properties.

beginner

In TypeScript, what is a simple approach to find the inorder predecessor of a node in a BST?

Traverse to the left child, then keep moving right until no more right child exists. If no left child, use parent pointers to find the predecessor. This can be done with a loop and conditional checks.

What is the inorder predecessor of a node with a left subtree in a BST?

A The leftmost node in the right subtree

B The rightmost node in the left subtree

C The root node

D The parent node always

The inorder predecessor is the rightmost (maximum) node in the left subtree.

If a node has no left subtree, how do you find its inorder predecessor?

A Move up to the parent until the node is a right child

B Go to the right child

C Go to the left child

D There is no predecessor

You move up the tree until you find a node that is a right child of its parent; that parent is the predecessor.

Why is the inorder predecessor useful in BST deletion?

A It balances the tree

B It helps find the smallest node

C It deletes the root node

D It helps replace a node to maintain BST order

Replacing a node with its inorder predecessor maintains the BST property during deletion.

In inorder traversal, the predecessor of a node is:

A The previous node visited

B The next node visited

C The root node

D The leaf node

The inorder predecessor is the node visited immediately before the current node in inorder traversal.

Which of these is NOT true about inorder predecessor?

A It is always smaller than the node

B It can be found in the left subtree

C It is always the parent node

D It is the largest node smaller than the given node

The inorder predecessor is not always the parent; it depends on the tree structure.

Explain how to find the inorder predecessor of a node in a BST with and without a left subtree.

Think about the inorder traversal order and how predecessor relates to it.

Describe why the inorder predecessor is important when deleting a node from a BST.

Consider how BST properties must stay true after deletion.