Lowest Common Ancestor of a BST

1package pkg5leetcode.blind75;2 3/*4 * Lowest Common Ancestor of a BST | LC 2355 * APPROACH: Walk from root using BST ordering to split p and q.6 * COMPLEXITY: Time O(h), Space O(1)7 */8public class blind75_LC235LowestCommonAncestorOfBST {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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {18        while (root != null) {19            if (p.val < root.val && q.val < root.val) root = root.left;20            else if (p.val > root.val && q.val > root.val) root = root.right;21            else return root;22        }23        return null;24    }25 26    public static void main(String[] args) {27        TreeNode root = new TreeNode(6);28        root.left = new TreeNode(2);29        root.right = new TreeNode(8);30        root.left.left = new TreeNode(0);31        root.left.right = new TreeNode(4);32        root.left.right.left = new TreeNode(3);33        root.left.right.right = new TreeNode(5);34        TreeNode p = root.left, q = root.right;35        check(lowestCommonAncestor(root, p, q).val == 6, "case1");36        TreeNode p2 = root.left.right, q2 = root.left.right.right;37        check(lowestCommonAncestor(root, p2, q2).val == 4, "case2");38        System.out.println("all tests passed");39    }40 41    static void check(boolean cond, String name) {42        if (!cond) throw new AssertionError("FAILED: " + name);43        System.out.println("  PASS " + name);44    }45}