Leetcode 103. 107. Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

BFS Approach 1


class Solution {
	public List> levelOrderBottom(TreeNode root) {

		List> flist = new ArrayList<>();
		List tlist = new ArrayList<>();

		if (root == null)
			return flist;

		Queue q = new LinkedList<>();
		q.add(root);
		q.add(null);

		while (!q.isEmpty()) {
			TreeNode curr = q.poll();

			if (curr == null) {
				flist.add(tlist);
				tlist = new ArrayList<>();

				if (q.isEmpty())
					break;
				else {
					q.add(null);
					continue;
				}
			}
			tlist.add(curr.val);
			if (curr.left != null)
				q.add(curr.left);
			if (curr.right != null)
				q.add(curr.right);
		}
		Collections.reverse(flist);
		return flist;
	}
}

Time Complexity: and Space Complexity:

See Video lecture

Leetcode 107. Binary Tree Level Order Traversal II

Introduction

Binary Tree Level Order Traversal II is a variation of the standard level order traversal of a binary tree. In this version, instead of traversing the tree level by level from top to bottom, we return the levels from bottom to top. This problem is commonly asked in coding interviews and helps in understanding tree traversal and queue-based algorithms.

Problem Statement

Given the root of a binary tree, return its nodes' values in a bottom-up level order traversal (from left to right, level by level starting from the last level).

Example

Consider the following binary tree:

The expected output for the bottom-up level order traversal is:

Approach

The most common approach to solving this problem is to perform a level order traversal using a queue and store the nodes of each level. Once all levels are traversed, reverse the order of levels to achieve the bottom-up order.

Steps to Solve

Initialize a queue to perform a breadth-first traversal of the binary tree.
Use an outer loop to process each level of the tree.
For each level, iterate through the nodes in the queue, adding their values to a temporary list and their children to the queue for the next level.
Store the temporary list for each level in a result list.
Once the traversal is complete, reverse the result list to achieve the bottom-up order.

Implementation in Java

The following is a Java implementation of Binary Tree Level Order Traversal II:


import java.util.*;

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

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

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Queue queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }

            result.add(0, currentLevel); // Insert each level at the beginning
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity: O(n), for the queue and result list.

Recursive Approach

An alternative solution involves recursion. The idea is to traverse the tree and collect nodes at each depth level. At the end of the traversal, reverse the collected levels.

Implementation


import java.util.*;

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> result = new ArrayList<>();
        collectLevels(root, 0, result);
        Collections.reverse(result);
        return result;
    }

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

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

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

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

Applications

This traversal technique has practical uses in various scenarios:

Data Visualization: Displaying hierarchical data structures in reverse order.
Game Development: Processing game states from the deepest to the shallowest level.
Pathfinding Algorithms: Analyzing tree-like structures for decision-making processes.

Common Mistakes

Not checking for an empty tree, which may result in a NullPointerException.
Incorrectly reversing the order of levels after traversal.
Failing to initialize the result list or temporary lists properly.

Edge Cases

The tree is empty (return an empty list).
The tree has only one node (return a list with a single level).
The tree is highly unbalanced, such as a linked list.

Sample Output

Consider the binary tree:

The output is:

Conclusion

Binary Tree Level Order Traversal II is an important variation of tree traversal problems. By mastering this problem, you gain insights into breadth-first search and learn to manipulate tree data in different ways. Practice similar problems to deepen your understanding of tree algorithms and recursion.