Search in BST
Concepts and Basic Operations DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Search for a key in a Binary Search Tree (BST), Binary Search Tree, Tree Traversal, Algorithm, Time Complexity, Space Complexity, Iteration, Recursion, Node, binary search tree properties, iterative vs recursive, search algorithms, time complexity analysis, tree traversal, BST Properties, Searching.
Problem Statement Given the root of a Binary Search Tree (BST) and an integer key, determine if a node with the value key exists in the BST. Return True if such a node is found, otherwise return False. A Binary Search Tree (BST) is a rooted binary tree data structure with the following properties: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. There must be no duplicate keys in the tree. Input Specification The first line contains a sequence of integers representing the Binary Search Tree in a level order traversal. A value of 1 indicates a null child. The second line contains a single integer, key, the value to be searched for. Output Specification Output True if the key is found in the BST, otherwise output False. Sample Test Cases Example 1: Explanation: The BST represented is: The key 10 is present in the BST. Example 2: Explanation: The BST represented is: The key 3 is present in the BST.