Comprehensive Collection of Common Binary Tree Interview Questions and Solutions

The article begins with an overview of binary tree interview topics, grouping them into six major categories: judgment problems, construction problems, storage problems, search problems, distance problems, and mixed problems.

1. Judgment Problems

These include checking whether a binary tree is a BST, a complete binary tree, a balanced binary tree, or whether two trees are isomorphic. Multiple solutions are presented, such as brute‑force, one‑pass, and in‑order traversal methods, each accompanied by full C implementations.

int isBSTError(BTNode *root) { ... }

int isBSTUnefficient(BTNode *root) { ... }

int isBSTEfficient(BTNode *root, BTNode *left, BTNode *right) { ... }

int isBSTInOrder(BTNode *root, BTNode *prev) { ... }

2. Construction Problems

Given traversal sequences, the article shows how to rebuild a binary tree. It explains why preorder+inorder or inorder+postorder uniquely determine a tree, while preorder+postorder does not. Algorithms for building from preorder‑inorder and inorder‑postorder are provided.

BTNode *buildBTFromPreInOrder(int preorder[], int inorder[], int n, int offset, int count) { ... }

BTNode *buildBTFromInPostOrder(int postorder[], int inorder[], int n, int offset, int count) { ... }

3. Storage Problems

Methods for persisting a BST or a general binary tree to a file and restoring it are described. For BSTs, preorder traversal is used; for general trees, null markers (e.g., ‘#’) are stored.

void bstSave(BTNode *root, FILE *fp) { ... }

BTNode *bstRestore(FILE *fp) { ... }

void btSave(BTNode *root, FILE *fp) { ... }

BTNode *btRestore(BTNode *root, FILE *fp) { ... }

4. Search Problems

Includes finding the lowest common ancestor (LCA) in a BST and in a generic binary tree, with both top‑down (O(N²)) and bottom‑up (O(N)) approaches.

BTNode *bstLCA(BTNode *root, BTNode *p, BTNode *q) { ... }

BTNode *btLCADown2Top(BTNode *root, BTNode *p, BTNode *q) { ... }

5. Distance Problems

Techniques for computing the shortest path between two nodes in a binary tree or BST, as well as the tree’s diameter, maximum width, and maximum distance between any two nodes, are covered.

int distanceOf2BTNodes(BTNode *root, BTNode *p, BTNode *q) { ... }

int btMaxDistance(BTNode *root, int *maxDepth) { ... }

int btMaxWidth(BTNode *root) { ... }

6. Mixed Problems

Examples combine binary trees with other data structures, such as building a balanced BST from a sorted array or a sorted singly‑linked list, and converting a BST into a doubly‑linked circular list.

BTNode *sortedArray2BST(int a[], int start, int end) { ... }

BTNode *sortedList2BST(ListNode **pList, int start, int end) { ... }

void bt2DoublyList(BTNode *node, BTNode **pPrev, BTNode **pHead) { ... }

Overall, the article serves as a detailed reference for common binary‑tree interview questions, offering clear explanations, multiple algorithmic strategies, and ready‑to‑use C code snippets.