Interview OS
Back to Algorithms & Data Structures

Library

Trees & BSTs

Hierarchies and ordered search.

Hierarchical

Overview

Trees are hierarchical structures where each node has children. This topic covers shape (binary, BST, balanced) and the traversals and invariants that give ordered iteration, fast search, and range queries.

How it works

Hierarchical
RootBSTBalanceOutputEntrynodeOrderedsearchRotationsrebalanceUse
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Entry

    • Hierarchical parent-to-children links.
  2. 2

    Ordered

    • left < node < right gives O(log n).
  3. 3

    Rotations

    • AVL/red-black keep height ~log n.
  4. 4

    Use

    • Sorted maps and range queries.
    • Example: TreeMap

Overview

Binary trees model hierarchy; BSTs keep left<root<right for O(log n) search when balanced.

When to use it

  • Range queries
  • Ordered iteration
  • Autocomplete prefixes (tries)

Reference

// In-order traversal yields sorted order for a BST
function inorder(n,out=[]){ if(!n) return out; inorder(n.left,out); out.push(n.val); inorder(n.right,out); return out; }

Common pitfalls

  • Assuming balance (skewed = O(n))
  • Mutating during traversal

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides