Solving Binary Tree Level Order Traversal

To see the question, click here.

Naive Approach

The idea is to determine the tree's height and then, for each level from 1 to the tree's height, gather the nodes at that level and add them to the result list.

// TC: O(nh)
// SC: O(n)

import java.util.List;
import java.util.ArrayList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeLevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        int height = treeHeight(root);
        for (int i = 1; i <= height; i++) {
            List<Integer> currentLevel = new ArrayList<>();
            collectNodesAtLevel(root, i, currentLevel);
            result.add(currentLevel);
        }
        return result;
    }

    private int treeHeight(TreeNode node) {
        if (node == null)
            return 0;
        return 1 + Math.max(treeHeight(node.left), treeHeight(node.right));
    }

    private void collectNodesAtLevel(TreeNode node, int level, List<Integer> list) {
        if (node == null)
            return;
        if (level == 1) {
            list.add(node.val);
        } else if (level > 1) {
            collectNodesAtLevel(node.left, level - 1, list);
            collectNodesAtLevel(node.right, level - 1, list);
        }
    }

    public static void main(String args[]) {
        BinaryTreeLevelOrderTraversal btlot = new BinaryTreeLevelOrderTraversal();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(btlot.levelOrder(root));
    }
}

Performance

The time complexity of the levelOrder the method is O(nh), where h = n for the worst-case unbalanced tree, and h = logn for a balanced tree. This is because, for each level of the tree, we traverse all the nodes at that level to collect their values. The space complexity of this solution is O(n). This is due to the storage of nodes in lists and the potential size of the call stack for an unbalanced tree.

Refined Approach

The idea is to implement a level-order traversal of a binary tree using a Queue, which is an efficient and standard approach.

// TC: O(n)
// SC: O(n)

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeLevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null)
            return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                temp.add(curr.val);
                if (curr.left != null)
                    queue.add(curr.left);
                if (curr.right != null)
                    queue.add(curr.right);
            }
            result.add(temp);
        }
        return result;
    }

    public static void main(String args[]) {
        BinaryTreeLevelOrderTraversal btlot = new BinaryTreeLevelOrderTraversal();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(btlot.levelOrder(root));
    }
}

Performance

The time complexity of the levelOrder method is O(n) because we visit each node in the binary tree once. The space complexity is also O(n) because, in the worst-case scenario, the queue can hold all the nodes at a particular binary tree level.

Efficient Approach

Let us do a preorder traversal (root, left, right) to visit each node in the binary tree. During the traversal, we keep track of the current level of the tree and add each node's value to the corresponding level in the result list. This ensures that nodes are grouped by their levels in the final output.

// TC: O(n)
// SC: O(n)

import java.util.List;
import java.util.ArrayList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeLevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        preorderTraversal(root, 0, result);

        return result;
    }

    private void preorderTraversal(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }

        result.get(level).add(node.val);

        preorderTraversal(node.left, level + 1, result);
        preorderTraversal(node.right, level + 1, result);
    }

    public static void main(String args[]) {
        BinaryTreeLevelOrderTraversal btlot = new BinaryTreeLevelOrderTraversal();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(btlot.levelOrder(root));
    }
}

Performance

The time complexity of the levelOrder method is O(n). This is because we visit each node once in a pre-order traversal. The space complexity is also O(n) because we use a recursive approach to traverse the tree and store the result in a result list. The space required for the recursive call stack is proportional to the tree's height, which can be at most n in the worst-case scenario for a skewed tree.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.