Where it runs
1. The problem
Back at step 68 there was a warning. Insert the numbers 1, 2, 3, 4, 5 into a plain BST in that order, and every new value goes to the right. The tree stretches into a chain of height n, and search slows down from O(log n) to O(n). This is not a rare accident. Data often arrives already sorted or almost sorted: timestamps, IDs that a database hands out in increasing order, names in alphabetical order. So before you can fix a lopsided tree, you need to measure how lopsided it is. And you need to catch the case where the top looks even while the tilt sits lower down.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that check whether a tree is balanced or build one that is. Compute heights bottom up in one pass, and build from sorted data by putting the middle at the root.
The lesson's isBalanced, with the helper returning a height or a signal that the tree is already unbalanced.
The middle element becomes the root and each half builds a subtree, so heights differ by at most 1.
The same build from a linked list, finding the middle with slow and fast pointers.