700. Search in a Binary Search Tree

Description of 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 1:

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

Example 2:

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

Constraints:

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 10^7
root is a binary search tree.
1 <= val <= 10^7

Solution

Tags: Rust Tree Binary Search Tree

Code (C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* curr = root;

        while(curr != nullptr && val != curr->val){
            if (val < curr->val) {
                curr = curr->left;
            }
            else if (val > curr->val) {
                curr = curr->right;
            }
        }

        return curr;
    }
};

Code (Rust)

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
        let mut curr = root;
        while let Some(ref node) = curr.clone() {
            let node = node.borrow();
            if val == node.val {
                break;
            }else if val < node.val {
                curr = node.left.clone();
            }else {
                curr = node.right.clone();;
            }   
        }
        return curr;
    }
}

Complexity

n is the number of element in the tree

Time Complexity

\(T(n) = \Theta(\log_2 (n)) \)

Auxiliary Space

\(S(n) = O(\log_2 (n)) \)

Leetbook