Algorithms for solving Binary Tree questions

A binary tree is a tree data structure in which a node has up to two children nodes, left and right. The first node of a binary tree is usually called root, and the nodes that have no children are usually called leaves. The number of levels in a binary tree is usually called height.

There are many classifications for binary trees, for example a perfect binary tree is one where all nodes have two children except the last leaf nodes, a balanced binary tree is one where the difference in height between the left and right subtrees is not greater than 1 level. In Leetcode, most of the binary tree questions deal with Binary Search Tree, which are binary trees where the left child always has a lesser value than the node itself, and the right child always has a greater one.

In this article, I want to summarize some of the algorithms used for solving binary tree questions:

Depth First Search (DFS)

Depth First Search, or DFS, is an algorithm to traverse (to visit) all the nodes in graph-like structures. DFS traverses a binary tree vertically, checking all the nodes along one branch from the root to a leaf before backtracking to explore other branches. This approach allows DFS to fully explore the depth of one subtree before moving to another. It’s a common algorithm for traverse graphs, it uses a stack to add the nodes to be traversed and keeps a list of visited nodes to avoid visiting the same node twice, however since binary trees don’t have cycles, we don’t need to keep track of the visited nodes :

function dfs(root) {
    if (!root) return [];
    const stack = [root];
    const result = [];

    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);

        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }

    return result;
}

In here we are adding the values of every node in the tree to an array and returning it.

The order we add the nodes to the stack define the kind of traversal : preorder, inorder and postorder.

Preorder

The current algorithm we have performs a preorder traversal, it follows the order root->left-right to visit the nodes in the tree, meaning that the root node is visited first, than the left node and its subtree, then the right node. However, for easier understanding and readability, it’s much better to use a recursive approach :

const preorderTraversal = function(root) {
    const result = [];

    const dfs = (node) => {
        if(!node) return;

        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }

    dfs(root);

    return result;
};

Inorder

In inorder traversal, we traverse the tree sweeping from the leftmost node to the right, following the order left->root->right so we need to change the order of our recursive calls:

const inOrderTraversal = function (root) {
    const result = [];

    const dfs = node => {
        if (!node) return;

        dfs(node.left);
        result.push(node.val); //add the root node after traversing the left side
        dfs(node.right);
    };

    dfs(root);

    return result;
};

In the resulting array, everything to the left of the root value belongs to the left subtree, everything to the right of the root belongs to the right subtree

Postorder

In postorder traversal, we visit the nodes following the order left->right->root, so we need to adjust the order of our recursive calls, once again :

const postOrderTraversal = function (root) {  
    const result = [];

    const dfs = node => {
        if (!node) return;

        dfs(node.left);
        dfs(node.right);
        result.push(node.val); //add the root node after traversing the left and right side
    };

    dfs(root);

    return result;
}

In this way, in the result array, the root will be the last item.

Breadth First Search (BFS)

Breadth First Search, or BFS, is an algorithm that traverses a graph-like structure by visiting a node’s closest neighbors first. In a binary tree BFS traverses the tree level by level using a queue data structure to keep track of nodes at the current level before moving to the next. This level-order traversal is useful for applications that need to process nodes layer by layer, such as finding the shortest path, calculating distances, or gathering nodes at each depth.

function bfs(root) {
    const queue = [root];
    const result = [];

    while (queue.length) {
        const length = queue.length;

        for (let i = 0; i < length; i++) {
            const node = queue.shift();
            result.push(node.val);
            if (node.left) {
                queue.push(node.left);
            }

            if (node.right) {
                queue.push(node.right);
            }
        }
    }

    return result;
}