LeetCode #700 Search in a Binary Search Tree

Easy

Problem

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.

Solution — Recursion

By comparing value of node and val, we can decide which child should be go down.

Complexity

Because it will traverse node from root to a leaf, it’s time complexity is O(h) if h denotes to the length of the longest path from root to leaves in this tree. Or you can say O(logn) because h is bounded by logn.

For space complexity, because the number of calls will reach at most h, it needs O(h) (or O(logn)) extra space.

Solution — Iteration

The same idea as recursion approach but use a while loop to achieve it.

Complexity

Because it’s used the same idea with recursion approach, it’s time complexity is O(h) (or O(logn)).

But it’s trivial to know that space complexity is only O(1).