Binary Tree Level Order Traversal Ii

                                            
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            
            for (int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                level.push_back(curr->val);
                
                if (curr->left) {
                    q.push(curr->left);
                }
                
                if (curr->right) {
                    q.push(curr->right);
                }
            }
            
            result.insert(result.begin(), level);
        }
        
        return result;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public 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 Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currLevel = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currLevel.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            result.add(0, currLevel);
        }
        
        return result;
    }
}

                                            
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):

class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            size = len(queue)
            level_vals = []
            
            for _ in range(size):
                node = queue.pop(0)
                level_vals.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.insert(0, level_vals)
        
        return result

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int getHeight(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

void getLevelNodes(struct TreeNode* root, int level, int* levelSize, int** result){
    if(root == NULL){
        return;
    }
    
    result[level][levelSize[level]++] = root->val;
    
    getLevelNodes(root->left, level - 1, levelSize, result);
    getLevelNodes(root->right, level - 1, levelSize, result);
}

int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int height = getHeight(root);
    
    *returnSize = height;
    
    int** result = (int**)malloc(sizeof(int*) * height);
    *returnColumnSizes = (int*)malloc(sizeof(int) * height);
    
    for(int i=0; i<height; i++){
        result[i] = (int*)malloc(sizeof(int) * 2000);
        (*returnColumnSizes)[i] = 0;
    }
    
    getLevelNodes(root, height - 1, *returnColumnSizes, result);
    
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> LevelOrderBottom(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while(queue.Count > 0) {
            int levelSize = queue.Count;
            IList<int> currentLevel = new List<int>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                currentLevel.Add(node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            result.Insert(0, currentLevel);
        }
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var levelOrderBottom = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length) {
        const level = [];
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.unshift(level);
    }
    
    return result;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 */
function levelOrderBottom(root: TreeNode | null): number[][] {
    const result: number[][] = [];
    if (!root) {
        return result;
    }
    
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const level: number[] = [];
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node) {
                level.push(node.val);
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
        }
        result.unshift(level);
    }
    
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrderBottom($root) {
        $result = [];
        if ($root === null) {
            return $result;
        }
        
        $queue = [];
        array_push($queue, $root);
        
        while (!empty($queue)) {
            $level = [];
            $size = count($queue);
            
            for ($i = 0; $i < $size; $i++) {
                $node = array_shift($queue);
                $level[] = $node->val;
                
                if ($node->left !== null) {
                    array_push($queue, $node->left);
                }
                
                if ($node->right !== null) {
                    array_push($queue, $node->right);
                }
            }
            
            array_unshift($result, $level);
        }
        
        return $result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    
    var result [][]int
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        var level []int
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            
            level = append(level, node.Val)
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append([][]int{level}, result...)
    }
    
    return result
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def level_order_bottom(root)
    return [] if root.nil?
    result = []
    queue = [root]

    while !queue.empty?
        level_size = queue.size
        level_nodes = []

        level_size.times do
            node = queue.shift
            level_nodes << node.val

            queue << node.left if node.left
            queue << node.right if node.right
        end

        result.unshift(level_nodes)
    end

    result
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode 
= null, _right: TreeNode = null) {
 *     var value: Int = _value
 *     var left: TreeNode = _left
 *     var right: TreeNode = _right
 * }
 */
object Solution {
    def levelOrderBottom(root: TreeNode): List[List[Int]] = {
        import scala.collection.mutable.Queue
        if (root == null) return List()

        val result = scala.collection.mutable.ListBuffer[List[Int]]()
        val queue = Queue[TreeNode]()

        queue.enqueue(root)

        while (queue.nonEmpty) {
            val level = scala.collection.mutable.ListBuffer[Int]()
            val size = queue.size

            for (_ <- 0 until size) {
                val node = queue.dequeue()
                level += node.value
                if (node.left != null) queue.enqueue(node.left)
                if (node.right != null) queue.enqueue(node.right)
            }

            result.prepend(level.toList)
        }

        result.toList
    }
}

To solve this coding challenge, we need to perform a bottom-up level order traversal of a binary tree. This means that we retrieve and store node values starting from the leaves of the tree up to the root, while processing each level from left to right. Here is an elucidated approach:

Explanation

Understand the Problem Statement :

Given a binary tree, we need to return the node values level by level, starting from the bottom-most level up to the root. Each level should be processed from left to right.
Tree nodes can contain values between -1000 and 1000, and the tree can have up to 2000 nodes.

Approach :

BFS (Breadth-First Search) strategy is ideal for level-order traversal. We will use a queue to facilitate the BFS.
Start from the root node. If the tree is empty (i.e., root is
null

), return an empty list.
Use a queue to track nodes level by level:

Enqueue the root node initially.
Process nodes level by level: for each node, enqueue its left child and right child (if they exist).

Store each level's values in a temporary list, and then store that list at the beginning of the result list. This way, the first processed level (root level) ends up being the last element in the result list.

Detailed Steps in Pseudocode :

Initialize an empty queue and enqueue the root node.
Initialize an empty result list.
While the queue is not empty:

Record the number of elements currently in the queue (this represents the number of nodes at the current level).
Initialize a temporary list to store current level’s node values.
Dequeue each node, store its value, and enqueue its children (left and right).
After processing all nodes at the current level, insert the temporary list of node values at the beginning of the result list.

Finally, return the result list.

Example Walkthrough :

Consider the example
[3,9,20,null,null,15,7]

.
Level 0 (root):
[3]
Level 1:
[9, 20]
Level 2:
[15, 7]
Output Order (from bottom to top):
[[15, 7], [9, 20], [3]]

Pseudocode Explanation

                                            
# Function to perform bottom-up level order traversal

Function levelOrderBottom(root):

    # If the root is null, return an empty list
    If root is null:
        return []

    # Initialize the result list which will store the final level order traversal bottom-up
    result = []
    
    # Initialize the queue with the root node
    queue = [root]
    
    # Loop until the queue is empty
    While queue is not empty:
        
        # Number of nodes at the current level
        size = length of queue
        
        # Temporary list to store node values at the current level
        level_values = []
        
        # Process all nodes at the current level
        For i in range from 0 to size - 1:
            # Dequeue the node from the front of the queue
            node = dequeue(queue)
            
            # Add the node's value to the current level's list
            level_values.append(node.value)
            
            # Enqueue the left child if it exists
            If node.left is not null:
                enqueue(queue, node.left)
                
            # Enqueue the right child if it exists
            If node.right is not null:
                enqueue(queue, node.right)
        
        # Insert the current level's list at the beginning of the result list
        insert result at index 0 with level_values
    
    # Return the final result
    return result

By deploying this methodical approach, you ensure that node values are processed level by level, and collected from the bottom-most level up to the root level. All nodes are managed within a queue to facilitate Breadth-First Search traversal, and the resultant levels are prepended to the result list to achieve the bottom-up ordering.