Binary Search Tree BST Java | Fresher Interview

A binary search tree is a binary tree with an ordering invariant. For every node, all the values in its left subtree are smaller than the node, and all the values in its right subtree are larger. The crucial word there is every, and it applies to the whole subtree, not just the immediate left and right children. A common mistake when validating a BST is to only compare a node with its direct children, which misses violations deeper down. The correct check passes a valid range down the recursion: each node must fall within a low and high bound, and you tighten that bound as you go left or right. The payoff of the ordering rule is efficiency. Because I can decide at each node whether to go left or right, search, insert, and delete all run in O of h, where h is the height of the tree. When the tree is balanced, the height is about log n, so those operations are O of log n, which is the whole point of a BST. But here's the catch I always raise: if I insert already-sorted data into a naive BST, every new value goes to one side, and the tree degenerates into what's essentially a linked list with height n, so operations become O of n. That's exactly why self-balancing trees like AVL and red-black trees exist, they keep the height logarithmic. And one elegant property: an inorder traversal of a valid BST always produces the values in sorted order, which is both a neat consequence and a simple way to check validity.