#!/usr/bin/env python
# coding: utf-8

# <h1>700. Search in a Binary Search Tree</h1>
# <hr>
# 
# <!--Copy Paste Leetcode statement between-->
# <p>You are given the <code>root</code> of a binary search tree (BST) and an integer <code>val</code>.</p>
# 
# <p>Find the node in the BST that the node's value equals <code>val</code> and return the subtree rooted with that node. If such a node does not exist, return <code>null</code>.</p>
# 
# <p>&nbsp;</p>
# <p><strong>Example 1:</strong></p>
# <img alt="" src="./img1.jpeg" style="width: 422px; height: 302px;">
# <pre><strong>Input:</strong> root = [4,2,7,1,3], val = 2
# <strong>Output:</strong> [2,1,3]
# </pre>
# <p>&nbsp;</p>
# <p><strong>Example 2:</strong></p>
# <img alt="" src="./img2.jpeg" style="width: 422px; height: 302px;">
# <pre><strong>Input:</strong> root = [4,2,7,1,3], val = 5
# <strong>Output:</strong> []
# </pre>
# 
# <p>&nbsp;</p>
# <p><strong>Constraints:</strong></p>
# 
# <ul>
# 	<li>The number of nodes in the tree is in the range <code>[1, 5000]</code>.</li>
# 	<li><code>1 &lt;= Node.val &lt;= 10<sup>7</sup></code></li>
# 	<li><code>root</code> is a binary search tree.</li>
# 	<li><code>1 &lt;= val &lt;= 10<sup>7</sup></code></li>
# </ul>
# 
# <!--Copy Paste Leetcode statement between-->
# 
# <p>&nbsp;</p>
# <a href="https://leetcode.com/problems/search-in-a-binary-search-tree/">Source</a> 
# <hr>

# In[1]:


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


# <h4>Code</h4>

# In[ ]:


def search_bst(root, val):
    """Recursive approach."""
    if not root:
        return None
    if root.val == val:
        return root
    if val < root.val:
        return search_bst(root.left, val)
    if val > root.val:
        return search_bst(root.right, val)


# In[ ]:


def search_bst(root, val):
    """Alternative version of above solution."""
    if root and val < root.val:
        return search_bst(root.left, val)
    if root and val > root.val:
        return search_bst(root.right, val)
    return root