Search in a Binary Search Tree

Problem: You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Input: root = [4,2,7,1,3], val = 5
Output: []

Approach: It's a simple problem to solve where we can use pre order traversal. We can take advantage of this tree being  binary search tree. At every node, we take following steps:

• If node.value is equal to val, return node.
• If node.value is less than val , search on node's righ subtree.
• Else search on node's left subtree.
• If node is null return null.

That's all!

Implementation in C#:

    public TreeNode SearchBST(TreeNode root, int val)

    {

        if (root == null)

        {

            return null;

        }

        if (root.val == val)

        {

            return root;

        }

        return root.val < val ?

               this.SearchBST(root.right, val) :

               this.SearchBST(root.left, val);

    }

Complexity: Average: O(logn), Worst: O(n) where tree is linked list.