Interview Questions – Find the immediate lesser key than the given key in the binary search tree

Problem

Given a balanced binary search tree and node element E from the tree, find the immediate lesser element K. In case when the K is not present then return -1.

Example

[1] Given below binary search tree

           20
    10            30
 5      15     25     35

If E = 20 then K = 15

If E = 25 then K = 20

If E = 5 then K = -1

Constraints

[1] All BST keys are positive integers.

[2] E will always present in the BST.

Before checking the solution it is advisable to try once yourself and comeback here.

Solution

If you look at above example, what we need to do here is to do an in-order traversal of the tree and keep track of the previous element return it when E is found, nice! you got the solution. Can you think a bit more and tell me the runtime complexity of this solution it is O(n) right? Do you think this is efficient solution to the problem? actually not, we can do better.

So what should be done here then, if you think we can do search of an element in BST in O(log₂n). Building on that idea, when E is found in BST the K would be either the max(of the left subtree of E) Or first least element < E in parent chain of E. But how do you decide if we have to search the parent chain, it is quite simple. In case when max of the left subtree is -1. We keep on checking parent till we get a element < E. In case if there is no such element in parent chain we simply return -1.

package working.example.tech.InterviewQuestions;
import working.example.tech.interfaces.TestCaseRunner;
public class LesserElementBST implements TestCaseRunner {
class Node {
    Node left;
    Node right;
    Integer data;
    public Node(Integer data) {
        this.data = data;
        left = null;
        right = null;
    }
}
class BST {
     public void add(Node root, Node node) {
         if (root == null) {
             root = node;
         }
         if (root.data > node.data) {
             if (root.left == null) {
                 root.left = node;
             } else {
                 add(root.left, node);
             }
         } else {
             if (root.right == null) {
                 root.right = node;
             } else {
                 add(root.right, node);
             }
         }
     }
     public void printBST(Node root) {
         if(root == null) {
             return;
         }
         printBST(root.left);
         System.out.print(root.data + " ");
         printBST(root.right);
     }
     private Integer findMaxformLeftSubtree(Node root) {
         if (root == null) {
             return -1;
         }
         while(root.right != null) {
             root = root.right;
         }
         return root.data;
     }
     public Integer getLesserElementForE(int E, Node root) {
         if (root.data == E) {
             return findMaxformLeftSubtree(root.left);
         }
         Integer k;
         if (root.data > E) {
            k = getLesserElementForE(E, root.left);
         } else {
            k = getLesserElementForE(E, root.right);
         }
         if (k == -1 && root.data < E) {
             k = root.data;
         }
         return k;
     }
}
@Override
public void RunTest() {
    BST bst = new BST();
    Node root = new Node(20);
    bst.add(root, new Node(5));
    bst.add(root, new Node(15));
    bst.add(root, new Node(30));
    bst.add(root, new Node(25));
    bst.add(root, new Node(35));
    System.out.println(bst.getLesserElementForE(5, root));
}
@Override
public void showOut() {
    // No implementation
}
}

Complexity

Auxiliary space complexity: O(n)

Time complexity: O(log₂n)

where n is number of keys in the BST