Binary Trees & Binary Search Trees (BST) — Complete Guide

What is a Binary Tree?

A Binary Tree is a hierarchical non-linear data structure in which each node has at most two children, referred to as the left child and the right child.

        1          ← Root Node (Depth 0, Height 2)
       / \
      2   3        ← Internal Nodes
     / \
    4   5          ← Leaf Nodes (Height 0)

Key Terminology

• Root: The topmost node in the tree.
• Leaf Node: A node with no children (both left and right are null).
• Depth of a Node: The number of edges from the root to that node.
• Height of a Tree: The maximum number of edges on the path from the root to a leaf node.
• Full Binary Tree: Every node has either 0 or 2 children.
• Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
• Balanced Binary Tree: The height difference between the left and right subtrees of any node is at most 1 (e.g., AVL tree, Red-Black tree).

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree with an additional ordering property:

• The value of all nodes in the left subtree is strictly less than the node's value.
• The value of all nodes in the right subtree is strictly greater than the node's value.
• Both left and right subtrees must also be binary search trees.

       8
      / \
     3   10
    / \    \
   1   6    14

Crucial Property: Inorder traversal (Left → Root → Right) of a Binary Search Tree produces a sorted array in ascending order.

Tree Traversals

1. Depth-First Search (DFS)

• Inorder (Left, Root, Right): Used in BST to retrieve values in sorted order.
• Preorder (Root, Left, Right): Used to create a copy of the tree or serialize it.
• Postorder (Left, Right, Root): Used for deletion (bottom-up cleanup) or calculating node dependencies.

javascript
function inorder(root, res = []) {
    if (!root) return res;
    inorder(root.left, res);
    res.push(root.val);
    inorder(root.right, res);
    return res;
}

2. Breadth-First Search (BFS) / Level-Order Traversal

Explores the tree level by level from left to right using a Queue.

javascript
function levelOrder(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
}

Solved Problem 1: Maximum Depth of Binary Tree 🟢 Easy

Problem: Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).

javascript
function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Time: O(N) | Space: O(H) where H is the height of the tree (call stack).

Solved Problem 2: Lowest Common Ancestor (LCA) in BST 🟡 Medium

Problem: Given a Binary Search Tree (BST), find the lowest common ancestor of two given nodes p and q.

Intuition: Leverage the BST property!

• If both p.val and q.val are smaller than root.val, LCA must be in the left subtree.
• If both are greater than root.val, LCA must be in the right subtree.
• If one is smaller and the other is greater (or equals root.val), current node is the split point and hence the LCA!

javascript
function lowestCommonAncestor(root, p, q) {
    let curr = root;

    while (curr) {
        if (p.val < curr.val && q.val < curr.val) {
            curr = curr.left;
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right;
        } else {
            return curr; // Split point
        }
    }

    return null;
}

Time: O(H) | Space: O(1) iterative

Solved Problem 3: Diameter of Binary Tree 🟡 Medium

Problem: Find the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

javascript
function diameterOfBinaryTree(root) {
    let maxDiameter = 0;

    function height(node) {
        if (!node) return 0;

        const leftHeight = height(node.left);
        const rightHeight = height(node.right);

        // Path passing through this node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        return 1 + Math.max(leftHeight, rightHeight);
    }

    height(root);
    return maxDiameter;
}

Time: O(N) | Space: O(H)

Solved Problem 4: Validate Binary Search Tree 🟡 Medium

Problem: Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST).

javascript
function isValidBST(root, min = null, max = null) {
    if (!root) return true;

    if ((min !== null && root.val <= min) || (max !== null && root.val >= max)) {
        return false;
    }

    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

Frequently Asked Questions

Q: What is the difference between a Complete Binary Tree and a Full Binary Tree?
A: A Full Binary Tree requires every node to have 0 or 2 children (no nodes with 1 child). A Complete Binary Tree requires all levels to be completely filled except possibly the last level, which must be filled left-to-right.

Q: When does a BST degenerate into O(N) time complexity?
A: When elements are inserted in already sorted order (ascending or descending), the tree becomes a skewed linked list with height N, making search, insertion, and deletion O(N). Self-balancing BSTs (like AVL or Red-Black trees) prevent this by keeping height O(log N).

Q: Why does Inorder Traversal of a BST give sorted output?
A: Because Inorder visits Left → Root → Right. In a BST, everything on the left is smaller than the root, and everything on the right is larger. Visiting smaller elements first, then the root, then larger elements inherently processes nodes in sorted order.