Search in a Binary Search Tree

1package pkg5leetcode.official75;2 3/*4 * Search in a Binary Search Tree | LC 7005 * APPROACH: BST property walk left or right.6 * COMPLEXITY: Time O(h), Space O(1)7 */8public class official75_LC700SearchInABinarySearchTree {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static TreeNode searchBST(TreeNode root, int val) {18        while (root != null && root.val != val)19            root = val < root.val ? root.left : root.right;20        return root;21    }22 23    public static void main(String[] args) {24        TreeNode root = new TreeNode(4);25        root.left = new TreeNode(2); root.right = new TreeNode(7);26        root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);27        check(searchBST(root, 2).val == 2, "case1");28        check(searchBST(root, 5) == null, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}