BST Inorder Predecessor in DSA Go - 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 does not have a 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?

It helps in operations like deletion of a node by replacing the node with its inorder predecessor to maintain BST properties.

beginner

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

Traverse to the left child, then keep moving to the right child until no more right child exists. That node is the inorder predecessor.

What is the inorder predecessor of the smallest node in a BST?

A Its left child

B It has no inorder predecessor

C Its right child

D Its parent

The smallest node has no node smaller than it, so no inorder predecessor.

If a node has a left subtree, where do you look for its inorder predecessor?

A Root node

B Leftmost node in the right subtree

C Rightmost node in the left subtree

D Parent node

The inorder predecessor is the largest node smaller than the current node, found as the rightmost node in the left subtree.

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

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

B Go down to the left child

C Go to the right child

D It has no inorder predecessor

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

Why is the inorder predecessor useful when deleting a node in BST?

A It is always the root node

B It is the rightmost node in the right subtree

C It is the smallest node in the tree

D It replaces the deleted node to keep BST order

Replacing the deleted node with its inorder predecessor maintains the BST property.

In Go, which loop helps find the inorder predecessor in the left subtree?

A Loop moving right until no right child

B Loop moving left until no left child

C Loop moving up to parent

D Loop moving down to root

You move right repeatedly in the left subtree to find the maximum node, which is the inorder predecessor.

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 nodes relate.

Describe why the inorder predecessor is important in BST node deletion.

Consider what happens when you remove a node with two children.