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

1. Introduction to Binary Trees

A Binary Tree is a hierarchical, non-linear data structure composed of Nodes connected by directed edges. Each node contains a data payload and at most two child references, traditionally termed the Left Child and the Right Child.

+─────────────────────────────────────────────────────────────────────────────+
|                          BINARY TREE ANATOMY                                |
+─────────────────────────────────────────────────────────────────────────────+

                     [ 10 ]  <── Root Node (Depth = 0, Level = 1)
                    /      \
             [ 5 ]            [ 20 ]  <── Internal Nodes (Depth = 1, Level = 2)
            /     \          /      \
        [ 3 ]     [ 7 ]  [ 15 ]    [ 25 ]  <── Leaf Nodes (Depth = 2, Height = 0)

Essential Tree Terminology:

• Root: The topmost node of the tree with no parent edges.
• Leaf Node: A node with zero children (left == NULL and right == NULL).
• Depth of a Node: The total number of edges from the tree root to that specific node.
• Height of a Node: The total number of edges on the longest downward path from that node to a leaf.
• Height of the Tree: The height of the root node (maximum depth among all nodes).
• Subtree: Any node in the tree along with all its descendants.

2. Taxonomy of Binary Trees

+─────────────────────────────────────────────────────────────────────────────+
|                         CLASSIFICATION OF BINARY TREES                      |
+─────────────────────────────────────────────────────────────────────────────+

 1. Full Binary Tree:           2. Complete Binary Tree:       3. Perfect Binary Tree:
    Every node has 0 or 2          All levels filled except       All internal nodes have 2
    children.                      last (filled left-to-right).   children; all leaves same level.

          [ 1 ]                          [ 1 ]                          [ 1 ]
        /       \                      /       \                      /       \
     [ 2 ]     [ 3 ]                [ 2 ]     [ 3 ]                [ 2 ]     [ 3 ]
              /     \              /     \    /                   /    \     /    \
           [ 4 ]   [ 5 ]        [ 4 ]   [ 5 ][ 6 ]             [ 4 ]  [ 5 ][ 6 ]  [ 7 ]

 4. Balanced Binary Tree (AVL / Red-Black):
    For every node, |Height(Left) - Height(Right)| <= 1. Guarantees O(log N) operations.

 5. Degenerate / Skewed Tree:
    Every parent node has only 1 child. Degenerates into a Linked List (O(N) operations!).

3. Binary Search Tree (BST) Fundamentals

A Binary Search Tree (BST) is a binary tree that satisfies the BST Invariant:

1. All node values in the Left Subtree are strictly less than the node's value: Val(Left) < Val(Node).
2. All node values in the Right Subtree are strictly greater than the node's value: Val(Right) > Val(Node).
3. Both left and right subtrees must themselves be valid Binary Search Trees.

+─────────────────────────────────────────────────────────────────────────────+
|                     BINARY SEARCH TREE (BST) LOOKUP FLOW                    |
+─────────────────────────────────────────────────────────────────────────────+

 Target Search: 7
                     [ 10 ]  ──> Is 7 < 10? YES: Go Left!
                    /      \
             [ 5 ]            [ 15 ]
            /     \
        [ 2 ]     [ 7 ]  ───> Is 7 == 7? MATCH FOUND in O(h) steps!

Crucial Property: An Inorder Traversal (Left -> Root -> Right) of any valid Binary Search Tree visits nodes in strictly sorted ascending order.

BST Deletion Algorithm (3 Cases):

1. Node is a Leaf (0 children): Simply delete the node and set parent's pointer to null.
2. Node has 1 Child: Replace the node with its child.
3. Node has 2 Children: Find the Inorder Successor (the smallest value in the right subtree) or Inorder Predecessor (largest in left subtree), copy its value to the target node, and recursively delete the successor from the subtree.

4. Tree Traversal Algorithms

+─────────────────────────────────────────────────────────────────────────────+
|                         TREE TRAVERSAL PARADIGMS                            |
+─────────────────────────────────────────────────────────────────────────────+

 Depth-First Search (DFS):
   1. Inorder:    Left ──> Root ──> Right   (Yields sorted order in BST)
   2. Preorder:   Root ──> Left ──> Right   (Ideal for Tree Serialization/Cloning)
   3. Postorder:  Left ──> Right ──> Root   (Ideal for Deletions & Bottom-up DP)

 Breadth-First Search (BFS):
   4. Level-Order: Explores nodes level-by-level using a FIFO Queue.

Advanced: Morris Inorder Traversal (O(1) Auxiliary Space)

Standard DFS traversals use O(h) memory on the recursion stack. Morris Traversal achieves O(N) time with strictly O(1) auxiliary space by temporarily creating threaded links from the rightmost node of the left subtree back to the current root!

5. Multi-Language Implementations & Syntax

C++ (TreeNode Definition & Traversals)

cpp
#include <iostream>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Inorder DFS: Left -> Root -> Right
void inorderDFS(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    inorderDFS(root->left, result);
    result.push_back(root->val);
    inorderDFS(root->right, result);
}

// Level-Order BFS: Queue-based
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> levels;
    if (!root) return levels;

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        std::vector<int> currentLevel;

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        levels.push_back(currentLevel);
    }
    return levels;
}

Java (TreeNode & Validations)

java
import java.util.*;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class TreeSolutions {
    // Validate Binary Search Tree using Min/Max Bounds
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long minBound, long maxBound) {
        if (node == null) return true;
        if (node.val <= minBound || node.val >= maxBound) return false;

        return validate(node.left, minBound, node.val) &&
               validate(node.right, node.val, maxBound);
    }
}

Python (TreeNode & Iterative Traversal)

python
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Iterative Inorder Traversal using explicit Stack
def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
    result, stack = [], []
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
            
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
        
    return result

JavaScript (TreeNode Class)

javascript
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

6. Time & Space Complexity Breakdown

7. Classic Interview Problems with Step-by-Step Solutions

Problem 1: Lowest Common Ancestor (LCA) in a Binary Tree

Problem Statement: Given a binary tree and two nodes p and q, find their Lowest Common Ancestor (LCA) node.

Step-by-Step Logic:

1. Base cases: If root is null, p, or q, return root.
2. Recursively search left subtree (leftLCA) and right subtree (rightLCA).
3. If both leftLCA and rightLCA return non-null values, p and q lie in opposite subtrees: therefore, current root is the LCA!
4. If only one side returns non-null, pass that result up.

javascript
function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    if (left && right) return root; // p and q found in different subtrees
    return left || right;           // Return whichever side found a target
}

• Time Complexity: O(N) — Visits each node once.
• Space Complexity: O(h) — Recursion call stack height.

Problem 2: Diameter of Binary Tree

Problem Statement: Find the length of the longest path between any two nodes in a tree. The path does not need to pass through the root.

Step-by-Step Logic:

1. For any node, the longest path passing through that node is Height(leftSubtree) + Height(rightSubtree).
2. Compute height bottom-up via DFS postorder.
3. Update a global maxDiameter variable at each node.

python
def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    max_diameter = 0

    def height(node):
        nonlocal max_diameter
        if not node:
            return 0
        
        lh = height(node.left)
        rh = height(node.right)
        
        # Diameter at current node is sum of left and right heights
        max_diameter = max(max_diameter, lh + rh)
        
        return 1 + max(lh, rh)

    height(root)
    return max_diameter

• Time Complexity: O(N) — Single postorder traversal.
• Space Complexity: O(h) auxiliary stack space.

8. Common Pitfalls & Interview Traps

1. Integer Overflow in BST Validation: Checking only left.val < root.val < right.val is insufficient. The entire left subtree must be less than root.val. Always maintain valid [minBound, maxBound] ranges, using 64-bit integers (long in Java/C++) to prevent overflow when nodes hold INT_MAX or INT_MIN.
2. Confusing Binary Tree Height with Diameter: Height is the distance from a node down to its furthest leaf. Diameter is the longest path between any two leaves in the tree.
3. Ignoring Skewed Tree Worst Cases: Always mention self-balancing trees (AVL or Red-Black Trees) in interviews when discussing worst-case O(N) BST degradation.

9. Frequently Asked Questions (FAQ)

Q1: What is the maximum number of nodes at level L in a binary tree?

A: At level L (where root is level 0), the maximum number of nodes is 2^L. The maximum total nodes in a binary tree of height h is 2^{h+1} - 1.

Q2: Why does Inorder Traversal of a BST yield sorted output?

A: Because Inorder traversal strictly follows Left -> Root -> Right. By the BST property, all elements in Left are smaller than Root, and all elements in Right are larger than Root, which recursively guarantees sorted ordering.

Q3: What is the difference between an AVL Tree and a Red-Black Tree?

A: Both are self-balancing binary search trees. AVL trees are more strictly balanced (height difference at most 1), providing faster lookups (O(log N)). Red-Black trees allow slightly looser balance, resulting in faster insertions and deletions with fewer rotations (used in C++ std::map and Java TreeMap).

Q4: How do you construct a unique Binary Tree from traversals?

A: You need Inorder Traversal combined with either Preorder or Postorder Traversal. Inorder is necessary to partition left and right subtrees, while Preorder/Postorder identifies the root.

Q5: What is Morris Traversal?

A: Morris Traversal is an advanced tree traversal algorithm that uses threaded binary trees to achieve O(N) time complexity and strictly O(1) auxiliary space without using recursion or an explicit stack.

Q6: Can a Binary Tree have cycles?

A: By definition, a tree is an undirected connected acyclic graph. If a cycle exists, it is no longer a valid tree—it is a general graph.