Binary Trees

Types of Binary Trees

  1. Full Binary Tree - Every node has either 0/2 children. (Not 1)

  2. Complete Binary Tree - All nodes are completely filled except the last level & the last level has all the nodes on as left as possible.

  3. Perfect Binary Tree - All leaf nodes are at the same level.

  4. Balanced Binary Tree - Height of tree at max log(N) [N = nodes]

  5. Degenerate Tree - basically, skewed.

Traversal Techniques

  1. Preorder traversal - Root -> left -> right

  2. In-order traversal - Left -> root -> right

  3. Post-order traversal - Left -> right -> root

  4. Level Order traversal (BFS) - level-wise

Breadth First Search (Level Order Traversal)

  1. When you think the answer may lie closer to the root node.

  2. When you are asked to search by level.

Maximum depth of Binary Tree

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root)  return 0;
        if (!root->left && !root->right)    return 1;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root)  return 0;

        queue<pair<TreeNode*, int>> q;
        q.push({root, 1});

        int level = 1;

        while (!q.empty()) {
            TreeNode* curr = q.front().first;
            int currLevel = q.front().second;
            level = max(level, currLevel);
            q.pop();

            if (curr->left) {
                q.push({curr->left, currLevel+1});
            }
            
            if (curr->right) {
                q.push({curr->right, currLevel + 1});
            }
        }

        return level;
    }
};

Balanced Binary Tree

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (!root)  return 0;
        if (!root->left && !root->right)    return 1;

        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }

    bool isBalanced(TreeNode* root) {
        if (!root)  return true;
        if (!root->left && !root->right)    return true;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        if (abs(leftDepth - rightDepth) > 1)    return false;
        else {
            return isBalanced(root->left)&&isBalanced(root->right);
        }
    }
};

Items left :

Last updated