LargestNumberSmallerInBinarySearchTree

Largest Number Smaller in Binary Search Tree

https://app.laicode.io/app/problem/136

Description

In a binary search tree, find the node containing the largest number smaller than the given target number.

If there is no such number, return INT_MIN.

Assumptions:

• The given root is not null.
• There are no duplicate keys in the binary search tree.

Examples

    5

  /    \

2      11

     /    \

    6     14

largest number smaller than 1 is Integer.MIN_VALUE(Java) or INT_MIN(c++)

largest number smaller than 10 is 6

largest number smaller than 6 is 5

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

For Example:

The sequence [1, 2, 3, #, #, 4] represents the following binary tree:

    1

  /   \

 2     3

      /

    4

Medium

Binary Search Tree

Assumption

The tree should not be null or empty

There should not be duplicates in the BST

Algorithm

This problem utilizes the classical BST traversal:

1. if (root.key > target) ⇒ go left
2. if (root.key < target) ⇒ go right

In this problem particularly, we maintain a global solution variable. This variable gets updated only when a node whose key is smaller than the target is met. Because this condition meets case 2, we need to go right. Since everything on the right of the node is larger than it, when we see another node < target in the right subtree of the current node, we can directly update the global solution.

Solution

Code

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public int largestSmaller(TreeNode root, int target) {
    // Write your solution here
    int result = Integer.MIN_VALUE;
    while (root != null) {
      if (root.key < target) {
        // Case 1: update the result
        result = root.key;
        root = root.right;
      } else {
        // Case 2: look for a smaller node
        root = root.left;
      }
    }
    return result;
  }
}

Complexity

Time:

On average, if the BST is balanced, traversal of the tree to a leaf node costs O(log(n)). In the worst case where the BST is flattened to a linked list, it is O(n). In either case, the complexity is O(height of the tree)

Space:

No additional data structures used ⇒ O(1)