## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Almost balanced trees

In the tree we just saw, every node's left and right subtrees are of the same height. This makes it a tree that is perfectly height-balanced. However, such trees are very rare; we come across them only when we have large trees with thousands of nodes.

Instead, we could try for trees that are either perfectly height-balanced or somewhere close to that. What do we mean by height-balanced? If the heights of any nodes, left or right subtrees, differ by at most 1, it is a height-balanced tree. The complexities of various operations would be almost the same as for a perfectly balanced tree.

In the preceding diagram, the left tree ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required