Search for an element in a binary search tree (BST)

700. Search in binary search tree

The difficulty is simple

Given a binary search tree （BST） The root node root And an integer value val.

You need to BST The node value found in is equal to val The node of . Return the subtree with this node as the root . If the node doesn't exist , Then return to null .

Ideas

For binary search trees （BST） Come on

• The value of the left child node is less than the value of the current node
• The value of the right child node is greater than the value of the current node

Therefore, for a specific node, we only need to judge the size relationship between the current node and the target value , Then continue to traverse

Does it look like a dichotomy ？ Actually BST The middle order traversal of is an ascending array ！

If you don't understand, please remember this conclusion , This is in the solution part and BST Relevant questions are very useful , for example

• The minimum absolute difference of binary search tree （ Use medium order traversal as an ordered array ）
• Find the mode in the binary search tree （ Use medium order traversal as an ordered array ）

package cn.edu.xjtu.carlWay.tree.searchInBinarySearchTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 700.  Search in binary search tree  *  Given a binary search tree （BST） The root node  root  And an integer value  val. * <p> *  You need to  BST  The node value found in is equal to  val  The node of .  Return the subtree with this node as the root .  If the node doesn't exist , Then return to  null . * <p> * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/ */
public class Solution {
    
    public TreeNode searchBST(TreeNode root, int val) {
    
        TreeNode node = root;
        while (node != null) {
    
            if (node.val == val) {
    
                return node;
            } else if (node.val > val) {
    
                node = node.left;
            } else {
    
                node = node.right;
            }
        }
        return null;
    }
}