Ceil in BST
Properties and Validation DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Ceiling of a given key in a Binary Search Tree (BST), Binary Search Tree, Traversal, Iteration, Time Complexity, Space Complexity, binary search tree operations, node properties, binary search tree properties, iterative vs recursive, time complexity analysis, tree traversal, Search in BST.
Problem Statement Given the root of a Binary Search Tree (BST) and an integer key, your task is to find the ceiling of the given key in the BST. The ceiling of a value key is defined as the smallest node value in the Binary Search Tree that is greater than or equal to the key. If no such node exists (i.e., all node values are smaller than the key), you should return 1. Input Specification The Binary Search Tree will be provided by its root node. The tree structure is implicit from the example inputs. Output Specification Return an integer representing the ceiling of the key. If no ceiling exists, return 1. Examples Example 1: Input: (Note: 1 represents a null child in the input representation, forming the BST: root=10, left=5, right=13, left.left=3, left.right=6, left.left.left=2, left.left.right=4, left.right.right=9, right.left=11, right.right=14) Output: Explanation: In the given BST, the smallest value greater than or equal to 8 is 9. Example 2: Input: (Note: 1 represents a null child in the input representation, forming the BST: root=8, left=5, right=12, left.left=4, left.right=7, left.right.left=6, right.left=10, right.right=14, right.right.left=13) Output: Explanation: In the given BST, the smallest value greater than or equal to 11 is 12.