E-commerce Giant (UAE) Hiring Drive — Online Assessment Question | Search an Element in BST

I encountered this problem in the Round 1 Online Assessment (OA) of an E‑commerce Giant (UAE) hiring drive conducted through AccioJob.

Sharing the problem and approach here for others preparing for online assessments, coding interviews, and DSA rounds.

Problem Statement

You are given a Binary Search Tree (BST) and a target integer k.

Determine whether the value k exists in the given Binary Search Tree.

Return:

• True / YES if the target value exists.
• False / NO if the target value does not exist.

Understanding the BST Property

A Binary Search Tree follows these rules:

• Every value in the left subtree is smaller than the current node's value.
• Every value in the right subtree is greater than the current node's value.

Because of this property, we don't need to traverse the entire tree.

At every node, we can decide which side of the tree can possibly contain the target.

Approach

Start from the root and compare the current node's value with the target k.

Case 1: Target Found

If:

curr.val == k

then the target exists, so return True.

Case 2: Target Is Smaller

If:

k < curr.val

then k can only exist in the left subtree.

Move to:

curr.left

Case 3: Target Is Greater

If:

k > curr.val

then k can only exist in the right subtree.

Move to:

curr.right

Case 4: Reached NULL

If the current node becomes None, the target does not exist in the BST.

Return False.

Algorithm

Set curr = root.
While curr is not None:
    If curr.val == k, return True.
    If k < curr.val, move to curr.left.
    Otherwise, move to curr.right.
If the loop ends, return False.

Python 3 Solution

def solve(root, k):
    curr = root
    while curr is not None:
        if curr.val == k:
            return True
        if k < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    return False

If the required output is YES / NO, we can use:

if solve(root, k):
    print("YES")
else:
    print("NO")

Complexity Analysis

Let H be the height of the BST.

Time Complexity

O(H)

At each step, we move to only one child.

For a balanced BST:

O(log N)

In the worst case, when the BST is completely skewed:

O(N)

Space Complexity

O(1) because we are using an iterative approach and no recursion stack or additional data structure.

Why BST Search Is Better Than Normal Traversal

If we used a normal DFS/BFS traversal, we might have to visit every node:

O(N)

But the BST property allows us to eliminate half of the possible direction at every decision in a balanced tree.

For example, if:

curr.val = 50
k = 30

we immediately know that 30 cannot be anywhere in the right subtree, so we only search the left subtree.

This was asked in the Round 1 Online Assessment of an E‑commerce Giant (UAE) hiring drive.

If anyone has encountered the same question or has a different/optimized approach, feel free to share it. It would be useful for others preparing for similar OA rounds.