Binary trees

A binary tree node has at most two children (left, right). Binary search trees order keys so left < root < right—enabling O(log n) search when balanced.

Terminology

• Root — top node
• Leaf — no children
• Height — longest path to leaf
• Full binary tree — each node 0 or 2 children

Node struct

#include 

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

int main() {
    TreeNode root{2, nullptr, nullptr};
    TreeNode left{1, nullptr, nullptr};
    TreeNode right{3, nullptr, nullptr};
    root.left = &left;
    root.right = &right;
    std::cout << "root=" << root.val << " left=" << root.left->val << "\n";
    return 0;
}

Balanced vs skewed

Skewed tree height n → operations degrade to O(n). AVL/red-black trees rebalance—STL std::map uses balanced tree internally.

Important interview questions and answers

1. Q: Binary tree vs BST?
   A: BST property on values; generic binary tree only caps children at two.
2. Q: Max nodes at height h?
   A: Up to 2^h leaves in a full level—guides recursion depth estimates.

Self-check

1. Define root, leaf, and height.
2. When does BST search become O(n)?

Pitfall: Skewed BST height n degrades to linked-list performance—mention balanced trees.