Algorithms 101: Ultimate Guide to Solving Binary Tree Coding Problems with Tips & Techniques

Binary Tree Problems and Solutions

1. Sum of Elements in a Binary Tree

Python Code:

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

def sum_of_elements(root):
    if root is None:
        return 0
    left_sum = sum_of_elements(root.left)
    right_sum = sum_of_elements(root.right)
    return root.value + left_sum + right_sum

JavaScript Code:

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

function sumOfElements(root) {
    if (root === null) {
        return 0;
    }
    const leftSum = sumOfElements(root.left);
    const rightSum = sumOfElements(root.right);
    return root.value + leftSum + rightSum;
}

Explanation:

• Both implementations compute the sum by recursively adding node values from the left and right subtrees.

2. Find Maximum Value in a Binary Tree

Python Code:

def find_max_value(root):
    if root is None:
        return float('-inf')
    left_max = find_max_value(root.left)
    right_max = find_max_value(root.right)
    return max(root.value, left_max, right_max)

JavaScript Code:

function findMaxValue(root) {
    if (root === null) {
        return -Infinity;
    }
    const leftMax = findMaxValue(root.left);
    const rightMax = findMaxValue(root.right);
    return Math.max(root.value, leftMax, rightMax);
}

Explanation:

• Both codes recursively find the maximum value among the current node and its subtrees.

3. Calculate Height of a Binary Tree

Python Code:

def calculate_height(root):
    if root is None:
        return 0
    left_height = calculate_height(root.left)
    right_height = calculate_height(root.right)
    return 1 + max(left_height, right_height)

JavaScript Code:

function calculateHeight(root) {
    if (root === null) {
        return 0;
    }
    const leftHeight = calculateHeight(root.left);
    const rightHeight = calculateHeight(root.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

Explanation:

• Both implementations compute the height by recursively finding the maximum height of the left and right subtrees.

4. Check if a Binary Tree is Balanced

Python Code:

def is_balanced(root):
    def check_height(node):
        if node is None:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    return check_height(root) != -1

JavaScript Code:

function isBalanced(root) {
    function checkHeight(node) {
        if (node === null) {
            return 0;
        }

        const leftHeight = checkHeight(node.left);
        if (leftHeight === -1) return -1;

        const rightHeight = checkHeight(node.right);
        if (rightHeight === -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

        return 1 + Math.max(leftHeight, rightHeight);
    }

    return checkHeight(root) !== -1;
}

Explanation:

• Both codes use a helper function to check the balance by calculating the height and checking if the difference between left and right subtree heights is within limits.

5. Find All Leaves at a Given Depth

Python Code:

def leaves_at_depth(root, depth):
    def collect_leaves(node, current_depth):
        if node is None:
            return []
        if current_depth == depth:
            return [node.value]
        return collect_leaves(node.left, current_depth + 1) + collect_leaves(node.right, current_depth + 1)

    return collect_leaves(root, 0)

JavaScript Code:

function leavesAtDepth(root, depth) {
    function collectLeaves(node, currentDepth) {
        if (node === null) {
            return [];
        }
        if (currentDepth === depth) {
            return [node.value];
        }
        return collectLeaves(node.left, currentDepth + 1).concat(collectLeaves(node.right, currentDepth + 1));
    }

    return collectLeaves(root, 0);
}

Explanation:

• Both implementations collect leaves at a specified depth by recursively traversing the tree and comparing the current depth.

6. Find the Lowest Common Ancestor (LCA)

Python Code:

def lowest_common_ancestor(root, p, q):
    if root is None or root == p or root == q:
        return root

    left_lca = lowest_common_ancestor(root.left, p, q)
    right_lca = lowest_common_ancestor(root.right, p, q)

    if left_lca and right_lca:
        return root

    return left_lca if left_lca else right_lca

JavaScript Code:

function lowestCommonAncestor(root, p, q) {
    if (root === null || root === p || root === q) {
        return root;
    }

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

    if (leftLca !== null && rightLca !== null) {
        return root;
    }

    return leftLca !== null ? leftLca : rightLca;
}

Explanation:

• Both implementations find the LCA by recursively searching for nodes p and q in left and right subtrees and determining if the current node is the LCA.

7. Find the Path from Root to a Given Node

Python Code:

def path_to_node(root, target):
    def find_path(node, path):
        if node is None:
            return False
        path.append(node.value)
        if node == target:
            return True
        if (find_path(node.left, path) or find_path(node.right, path)):
            return True
        path.pop()
        return False

    path = []
    find_path(root, path)
    return path

JavaScript Code:

function pathToNode(root, target) {
    function findPath(node, path) {
        if (node === null) {
            return false;
        }
        path.push(node.value);
        if (node === target) {
            return true;
        }
        if (findPath(node.left, path) || findPath(node.right, path)) {
            return true;
        }
        path.pop();
        return false;
    }

    const path = [];
    findPath(root, path);
    return path;
}

Explanation:

• Both codes use a helper function to build the path while searching for the target node, adding nodes to the path and backtracking if necessary.

8. Reverse a Binary Tree

Python Code:

def reverse_tree(root):
    if root is None:
        return
    root.left, root.right = root.right, root.left
    reverse_tree(root.left)
    reverse_tree(root.right)

JavaScript Code:

function reverseTree(root) {
    if (root === null) {
        return;
    }
    [root.left, root.right] = [root.right, root.left];
    reverseTree(root.left);
    reverseTree(root.right);
}

Explanation:

• Both implementations reverse the tree by swapping the left and right children of each node and recursively applying this operation to subtrees.

Summary of Tips:

1. Utilize Recursion: Many tree problems naturally involve recursion.
2. Handle Base Cases: Properly define base cases to avoid errors.
3. Combine Results: Aggregate results from subtrees to solve problems.
4. Optimize Performance: Use early termination and efficient traversal.
5. Ensure Correct Traversal: Accurate traversal and backtracking are crucial.

Recommend Resource

How to solve (almost) any binary tree coding problem Inside code