BSTPREDECR - Editorial

editorial
1

Prerequisites :- Binary Search Trees, BT traversals.

Problem :- Find the inorder predecessor of a given node X in a binary search tree. The inorder predecessor, denoted as node Y, is the node that immediately precedes X in the inorder traversal of the binary tree. If no such predecessor exists, return -1.

Solution Approach :-

The solution uses an iterative approach to find the inorder predecessor of a given node in a Binary Search Tree (BST). The key observation is that the inorder predecessor is the largest node in the left subtree of the given node (if it has a left subtree). If the given node doesn’t have a left subtree, we need to traverse up the tree until we find a node whose right child is an ancestor of the given node.

Algorithm:

    1. Initialize a pointer predecessor to NULL.
    1. Iterate through the tree:
    • If the current node’s value is less than the target value x, update the predecessor and move to the right subtree.
    • If the current node’s value is greater than or equal to x, move to the left subtree.
    1. After the iteration, if the predecessor is still NULL, return -1 as no predecessor exists. 4. Otherwise, return the value of the predecessor.

Time complexity: O(N), because in the worst case, the algorithm visits all the nodes in the given BST.

Space complexity: O(1), as no extra space is needed.

2

Unable to compile in Java

Main.java:43: error: class Codechef is public, should be declared in a file named Codechef.java
public class Codechef {

Codechef class is probably part of the hidden code. Kindly fix the issue.

3

t_sanjay fixed, check now. Thanks for reporting.

1 Like