700. Search in a Binary Search Tree

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

Recursive:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return root
        if root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

Iterative:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        while(root):
            if root.val == val:
                return root
            elif val < root.val:
                root = root.left
            else:
                root = root.right
        return root

Let's discuss the time complexity and space complexity of the search operation in a BST whose height is h. Focus on the recursion solution first. In the worse case, the depth of our recursion is equal to the height of the tree. Therefore, the time complexity of the recursion solution is O(h). And taking system stack into consideration, the space complexity should be O(h) in the worst case as well.

What about the iterative solution? The time complexity will be equal to the loop time which is also O(h) while the space complexity is O(1) since we do not need system stack anymore in an iterative solution.

Question:

If you do not know the height of the BST h but you are given the total number of nodes N of the BST, can you express the time complexity and space complexity using N instead of h?

Hint:

What's the difference of the relationship between N and h in the best case and the relationship in the worst case?

The time complexity is O(h). Or O(N) in the worst case and O(logN) ideally if the tree is well organized.

The space complexity is O(h). In other word, O(N) in the worst case and O(logN) ideally. If you implement the algorithm iteratively, the space complexity can be O(1).