Problem

In this problem, we aim to improve the search operation in a Binary Search Tree (BST). Specifically, we introduce the concept of a sentinel node. A sentinel node ensures that searches do not reach end-of-tree null values during traversal. Instead, each null child pointer is replaced with a reference to a sentinel node. This approach simplifies handling cases like searching for non-existing elements and reduces complexity in edge-case processing.

Examples

1
2
3
4
5
6
7

          8
        /   \
       3    10
      / \
     1   6
        / \
       4   7

Example 1

1
2
3
4

Input: Tree:  [8, 3, 10, 1, 6, null, null, null, null, 4, 7]
SentinelValue: -1
SearchKey: 4
Output: Node found with key: 4

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:
Tree: [8, 3, 10, 1, 6, null, null, null, null, 4, 7]
SentinelValue: -1
SearchKey: 9
Output:
Node not found. Sentinel reached with value: -1

Explanation:
The BST structure is the same as Example 1.
The search operation does not find the node with value 9 and stops at the sentinel node with a value of -1.

Solution

Method 1 - Using the sentinel

The traditional method of searching in a Binary Search Tree (BST) involves starting at the root and traversing the tree based on comparison with the target value. If the value is smaller, you move left; if it’s larger, you move right. The process stops either when the target is found or when a null node (representing a leaf) is reached.

Search without Sentinel

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class SearchWithoutSentinel {
    public static TreeNode search(TreeNode root, int key) {
        while (root != null) {
            if (root.val == key) {
                return root; // Node found
            }
            root = key < root.val ? root.left : root.right;
        }
        return null; // Not found
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);

        TreeNode result = search(root, 6);
        System.out.println(result != null ? "Node found with key: " + result.val : "Node not found");
    }
}
1
2
3
4
5
6
7

- **Conditional Statements**:
    - One `while` condition: `root != null`.
    - One check inside the loop: `key < root.val`.
    - Combined average of **2.5 checks** per iteration.

**Cost**:
On a tree with 1000 nodes, this results in roughly **2500 conditional checks** during traversal.

Using the sentinel

We can optimise this process by replacing null child pointers in the BST with a sentinel node — a special placeholder object with a unique value. During the search, the sentinel node guarantees a “hit” every time, either on an actual node or on the sentinel itself. This eliminates the need to explicitly handle null.

Optimised Sentinel Node Implementation
  1. Sentinel Node Introduction:
    • Use a static placeholder node (sentinel) for all leaf child pointers.
    • Before initiating a search, set sentinel.val to the target value.
  2. Benefits:
    • Reduces the number of conditional checks per iteration from an average of 2.5 to 2.
    • Saves 0.5 checks per iteration, which accumulates into significant performance benefits for large trees or frequent searches.
  3. Efficiency Gains:
    • On a tree with 1000 nodes, this method saves 500 conditional checks (from 2500 to 2000).

Advantages

  • Performance Gains: Saving 500 conditional checks over 1000 nodes is significant for large and frequently accessed trees.
  • Simplified Logic: No need to explicitly handle null (leaf) cases — always guaranteed a hit.
  • Use Cases:
    • Optimised traversal for trees with large sizes.
    • Scenarios with frequent searches, such as hot sections in code.

This improvement not only optimises conditional evaluations but also enhances clarity and reliability in tree traversal operations. For example, in high-performance applications requiring thousands of traversals, this method consistently outperforms traditional search mechanisms.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public class SearchWithSentinel {
    static TreeNode sentinel = new TreeNode(-1); // A static sentinel node
    
    public static TreeNode search(TreeNode root, int key) {
        sentinel.val = key; // Set the sentinel to the target value
        while (root != sentinel) {
            if (root.val == key) {
                return root; // Node found
            }
            root = key < root.val ? root.left : root.right;
        }
        return null; // Not found (guaranteed hit on sentinel, need additional check)
    }

    public static TreeNode insert(TreeNode root, int key) {
        if (root == null) {
            TreeNode newNode = new TreeNode(key);
            newNode.left = newNode.right = sentinel; // Leaf children point to sentinel
            return newNode;
        }
        if (key < root.val) {
            root.left = insert(root.left, key);
        } else if (key > root.val) {
            root.right = insert(root.right, key);
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = null;
        root = insert(root, 8);
        root = insert(root, 3);
        root = insert(root, 10);
        root = insert(root, 1);
        root = insert(root, 6);

        TreeNode result = search(root, 6);
        System.out.println(result != null ? "Node found with key: " + result.val : "Node not found");
        
        TreeNode notFoundResult = search(root, 15);
        System.out.println(notFoundResult != null ? "Node found with key: " + notFoundResult.val : "Node not found (sentinel reached)");
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class SentinelNode(TreeNode):
    def __init__(self, val):
        super().__init__(val)

class Solution:
    def __init__(self, sentinel_value):
        self.sentinel = SentinelNode(sentinel_value)
    
    def insert(self, root, key):
        if root is None:
            new_node = TreeNode(key)
            new_node.left = self.sentinel
            new_node.right = self.sentinel
            return new_node
        
        if key < root.val:
            root.left = self.insert(root.left, key)
        elif key > root.val:
            root.right = self.insert(root.right, key)
        return root

    def search(self, root, key):
        while root != self.sentinel:
            if root.val == key:
                return f"Node found with key: {key}"
            elif key < root.val:
                root = root.left
            else:
                root = root.right
        return f"Node not found. Sentinel reached with value: {self.sentinel.val}"

# Example usage
solution = Solution(sentinel_value=-1)
root = None
root = solution.insert(root, 8)
root = solution.insert(root, 3)
root = solution.insert(root, 10)
root = solution.insert(root, 1)
root = solution.insert(root, 6)
root = solution.insert(root, 4)
root = solution.insert(root, 7)

# Example searches
print(solution.search(root, 4))  # Node found with key: 4
print(solution.search(root, 9))  # Node not found. Sentinel reached with value: -1

Complexity

  • ⏰ Time complexity: O(h). The search operation involves traversing the height of the BST. For a balanced BST, the time complexity is O(log n). For a degenerate (unbalanced) tree, the complexity deteriorates to O(n).
  • 🧺 Space complexity: O(1). The space complexity is O(1) for iterative search since we use a constant amount of space. For recursive search, the space complexity is O(h) due to the recursion stack, where h is the height of the BST.