Leetcode

Search in a Binary Search Tree

  • Time:O(n)
  • Space:O(h)

C++

class Solution {
 public:
  TreeNode* searchBST(TreeNode* root, int val) {
    if (!root)
      return nullptr;
    if (root->val == val)
      return root;
    if (root->val > val)
      return searchBST(root->left, val);
    return searchBST(root->right, val);
  }
};

JAVA

public class Solution {
  public TreeNode searchBST(TreeNode root, int val) {
    if (root == null)
      return null;
    if (root.val == val)
      return root;
    if (root.val > val)
      return searchBST(root.left, val);
    return searchBST(root.right, val);
  }
}

Python

class Solution:
  def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
      return None
    if root.val == val:
      return root
    if root.val > val:
      return self.searchBST(root.left, val)
    return self.searchBST(root.right, val)