Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Binary Trees and BST

A tree is a hierarchy of nodes connected by edges, with no cycles. A binary tree gives each node at most two children: left and right.

        1          ← root (depth 0)
       / \
      2   3        ← depth 1
     / \   \
    4   5   6      ← leaves (no children)

Terms

Term Meaning
Root top node, no parent
Leaf node with no children
Depth of a node edges from the root to it
Height of a tree edges (or nodes, define it!) on the longest root-to-leaf path
Full binary tree every node has 0 or 2 children
Complete binary tree all levels full except maybe the last, filled left to right (heaps)
Perfect binary tree all levels completely full: 2ʰ⁺¹ − 1 nodes
Balanced heights of left and right subtrees differ by at most 1 everywhere → height O(log n)
struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

The four traversals

Traversal Order For the tree above Typical use
Preorder Root, Left, Right 1 2 4 5 3 6 copy / serialise a tree
Inorder Left, Root, Right 4 2 5 1 3 6 sorted order in a BST
Postorder Left, Right, Root 4 5 2 6 3 1 delete a tree, compute heights
Level order level by level (BFS) 1 2 3 4 5 6 shortest depth, views, zigzag
void inorder(TreeNode* n, vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);
    inorder(n->right, out);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();                  // nodes in this level
        res.push_back({});
        while (sz--) {
            TreeNode* n = q.front(); q.pop();
            res.back().push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
    }
    return res;
}

See them animated: inorder, preorder, postorder, level order.

The key recursive question

Most tree problems are solved by asking: "What does each child need to return to its parent?"

int height(TreeNode* n) {                       // nodes on the longest path
    if (!n) return 0;
    return 1 + max(height(n->left), height(n->right));
}

int best = 0;                                   // diameter: longest path between any two nodes (edges)
int depth(TreeNode* n) {
    if (!n) return 0;
    int l = depth(n->left), r = depth(n->right);
    best = max(best, l + r);                    // path through this node
    return 1 + max(l, r);                       // what the parent needs
}

Lowest common ancestor (binary tree)

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r) return root;                    // p and q are on different sides
    return l ? l : r;
}

Binary Search Tree (BST)

For every node: all values in the left subtree < node < all values in the right subtree. Inorder traversal of a BST gives sorted values.

TreeNode* insert(TreeNode* root, int v) {
    if (!root) return new TreeNode(v);
    if (v < root->val) root->left = insert(root->left, v);
    else root->right = insert(root->right, v);
    return root;
}
bool search(TreeNode* root, int v) {
    while (root) {
        if (v == root->val) return true;
        root = v < root->val ? root->left : root->right;
    }
    return false;
}

Delete has three cases: a leaf (remove it), one child (replace it with the child), two children (copy the inorder successor — the smallest node of the right subtree — and delete that instead).

Operation Balanced BST Skewed BST (like a linked list)
Search / insert / delete O(log n) O(n)

Self-balancing BSTs (AVL, Red-Black) keep the height O(log n) — C++ set/map and Java TreeMap are Red-Black trees.

Validate a BST: pass an allowed (min, max) range down the recursion — checking only a node against its children is a classic mistake.

Classic problems

Problem Idea
Max depth, diameter, balanced tree postorder: return height
Same tree / symmetric tree compare two trees in parallel
Level order, zigzag, right side view BFS level by level
Path sum / max path sum return the best downward path
LCA of binary tree / BST recursion (BST: use values)
Validate BST, kth smallest in BST inorder / ranges
Build tree from preorder + inorder root from preorder, split by inorder
Serialize / deserialize preorder with null markers

Practise in the Trees section.

Interview one-liners

More DSA notes