Implement a Binary Tree

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BinaryTree {
public:
    TreeNode* root;
    BinaryTree() : root(NULL) {}
};
            

Inorder Traversal of a Binary Tree

void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}
            

Preorder Traversal of a Binary Tree

void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}
            

Postorder Traversal of a Binary Tree

void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}
            

Check if a Binary Tree is Balanced

int height(TreeNode* root) {
    if (root == NULL) return 0;
    return max(height(root->left), height(root->right)) + 1;
}

bool isBalanced(TreeNode* root) {
    if (root == NULL) return true;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
            

Check if a Binary Tree is a Binary Search Tree (BST)

bool isBST(TreeNode* root, int minVal, int maxVal) {
    if (root == NULL) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
}
            

Find the Height of a Binary Tree

int height(TreeNode* root) {
    if (root == NULL) return 0;
    return max(height(root->left), height(root->right)) + 1;
}
            

Level Order Traversal of a Binary Tree

vector> levelOrder(TreeNode* root) {
    vector> result;
    if (root == NULL) return result;
    queue q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        vector level;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}
            

Convert a Binary Tree to a Doubly Linked List

TreeNode* head = NULL, *tail = NULL;

void convertToDLL(TreeNode* root) {
    if (root == NULL) return;
    convertToDLL(root->left);
    if (tail == NULL) {
        head = root;
    } else {
        tail->right = root;
        root->left = tail;
    }
    tail = root;
    convertToDLL(root->right);
}
            

Lowest Common Ancestor of a Binary Tree

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left == NULL) return right;
    if (right == NULL) return left;
    return root;
}
            

Serialize and Deserialize a Binary Tree

string serialize(TreeNode* root) {
    if (root == NULL) return "#";
    return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}

TreeNode* deserialize(string data) {
    stringstream ss(data);
    return deserializeHelper(ss);
}

TreeNode* deserializeHelper(stringstream& ss) {
    string val;
    getline(ss, val, ',');
    if (val == "#") return NULL;
    TreeNode* node = new TreeNode(stoi(val));
    node->left = deserializeHelper(ss);
    node->right = deserializeHelper(ss);
    return node;
}
            

Flatten a Binary Tree to a Linked List

void flatten(TreeNode* root) {
    if (root == NULL) return;
    if (root->left) {
        flatten(root->left);
        TreeNode* temp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = temp;
    }
    flatten(root->right);
}
            

Find the Diameter of a Binary Tree

int diameter = 0;

int findDiameter(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = findDiameter(root->left);
    int rightHeight = findDiameter(root->right);
    diameter = max(diameter, leftHeight + rightHeight);
    return max(leftHeight, rightHeight) + 1;
}

int getDiameter() {
    findDiameter(root);
    return diameter;
}
            

Construct a Binary Tree from Inorder and Preorder

TreeNode* buildTree(vector& inorder, vector& preorder) {
    unordered_map inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderMap[inorder[i]] = i;
    }
    return buildTreeHelper(preorder, inorderMap, 0, preorder.size() - 1, 0);
}

TreeNode* buildTreeHelper(vector& preorder, unordered_map& inorderMap, int preStart, int preEnd, int inStart) {
    if (preStart > preEnd) return NULL;
    TreeNode* root = new TreeNode(preorder[preStart]);
    int inIndex = inorderMap[root->val];
    root->left = buildTreeHelper(preorder, inorderMap, preStart + 1, preStart + inIndex - inStart, inStart);
    root->right = buildTreeHelper(preorder, inorderMap, preStart + inIndex - inStart + 1, preEnd, inIndex + 1);
    return root;
}