BST Inorder Predecessor in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the maximum value node in a BST subtree.

DSA C++

Node* findMax(Node* root) {
    while (root && root->[1]) {
        root = root->right;
    }
    return root;
}

Drag options to blanks, or click blank then click option'

Aleft

Bchild

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'left' instead of 'right' pointer to find maximum node.

Not checking if root is null before accessing pointers.

To find the maximum node in a BST subtree, we keep moving to the right child until there is no right child.

2fill in blank

medium

Complete the code to find the inorder predecessor when the left subtree exists.

DSA C++

Node* inorderPredecessor(Node* root) {
    if (root->left) {
        return findMax(root->[1]);
    }
    return nullptr;
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using right subtree instead of left subtree.

Returning nullptr without checking left subtree.

If the left subtree exists, the inorder predecessor is the maximum node in the left subtree.

3fill in blank

hard

Fix the error in the code to find the inorder predecessor when no left subtree exists.

DSA C++

Node* inorderPredecessor(Node* root) {
    if (!root->left) {
        Node* p = root->[1];
        while (p && root == p->left) {
            root = p;
            p = p->[1];
        }
        return p;
    }
    return findMax(root->left);
}

Drag options to blanks, or click blank then click option'

Aparent

Bchild

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using left or right pointers instead of parent to move up.

Not checking the condition in the while loop correctly.

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

4fill in blank

hard

Fill both blanks to complete the function that returns the inorder predecessor of a node in BST.

DSA C++

Node* inorderPredecessor(Node* root) {
    if (root->left) {
        return findMax(root->[1]);
    }
    Node* p = root->[2];
    while (p && root == p->left) {
        root = p;
        p = p->parent;
    }
    return p;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up left and right pointers.

Using wrong pointer to move up the tree.

If left subtree exists, predecessor is max in left subtree (use left pointer). Otherwise, move up using parent pointer.

5fill in blank

hard

Fill all three blanks to complete the code that finds the inorder predecessor in BST with parent pointers.

DSA C++

Node* inorderPredecessor(Node* root) {
    if (root->[1]) {
        return findMax(root->[2]);
    }
    Node* p = root->[3];
    while (p && root == p->left) {
        root = p;
        p = p->parent;
    }
    return p;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using right pointer instead of left for subtree.

Using wrong pointer to move up the tree.

The first blank checks if left subtree exists (left pointer). The second blank accesses left subtree to find max. The third blank moves up using parent pointer.