Jobs

Interviews

Discussions

Binary Tree Level Order Traversal

Medium

TikTok

1 view

Topics:

TreesGraphs

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Binary Tree Level Order Traversal

Medium

TikTok

1 view

Topics:

TreesGraphs

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node values in the binary tree?
Can the binary tree be empty (i.e., root is null)? If so, what should I return?
Are the node values guaranteed to be integers, or could they be other data types like floats?
Do I need to handle the case where the tree is very deep or wide, potentially leading to memory constraints?
Is there an upper bound on the number of nodes in the tree?

Brute Force Solution

Approach

We want to visit all nodes of the tree level by level. The brute force method is like exploring every single possible path to each level of the tree, without any particular strategy.

Here's how the algorithm would work step-by-step:

First, figure out the height of the tree. This tells us how many levels we have to visit.
Then, for each level, go through every single node in the tree and check if that node belongs to the current level.
If a node belongs to the current level, we add its value to a list representing that level.
We do this by checking all nodes for level 1, then all nodes for level 2, and so on, until we have processed all levels.
Finally, we put the lists for each level together, in order from top to bottom, to get the final level order traversal.

Code Implementation

def level_order_brute_force(root):
    def get_tree_height(node):
        if not node:
            return 0
        left_height = get_tree_height(node.left)
        right_height = get_tree_height(node.right)
        return max(left_height, right_height) + 1

    def get_nodes_at_level(node, level, current_level, level_nodes):
        if not node:
            return

        # If we've reached the target level, append the node's value.
        if current_level == level:
            level_nodes.append(node.val)
            return

        get_nodes_at_level(node.left, level, current_level + 1, level_nodes)
        get_nodes_at_level(node.right, level, current_level + 1, level_nodes)

    if not root:
        return []

    tree_height = get_tree_height(root)
    result = []

    # Iterate through each level of the tree.
    for level in range(1, tree_height + 1):

        level_nodes_list = []
        #For each level, retrieve the nodes at each level
        get_nodes_at_level(root, level, 1, level_nodes_list)

        result.append(level_nodes_list)

    return result

Big(O) Analysis

Time Complexity

O(n*h) – The algorithm first calculates the height of the tree, which in the worst case (e.g., a skewed tree) takes O(n) time, but if the tree is balanced takes O(log n) time which we'll account for at the end. The algorithm then iterates through each level of the tree, from 1 to h (the height), so the outer loop is O(h). For each level, it visits every node in the tree (n nodes) to check if that node belongs to the current level. Checking if a node belongs to the current level involves traversing from the root to that node. Each of these traversals takes at most O(h) time. So, the cost of visiting each level is O(n*h). Given that there are O(h) levels, the complexity would appear to be O(n*h*h). However, the height calculation has to be considered separately. With the height calculated in O(n) in the worst case, the dominant term becomes visiting all n nodes for each of the h levels i.e. O(n*h). Note, if the height calculation is performed inside of the level loop the time complexity would be O(n*h*n). In this case it occurs only once and doesn't contribute to the level loop time complexity. If we are dealing with a balanced tree the height would be O(log n), resulting in O(n log n) for the level calculations and O(log n) for the height calculation. In the worst case the tree is skewed and h = n so the total time complexity is O(n*n) i.e. O(n^2). If we consider a more balanced tree it would be closer to O(n log n). Without additional constraints, we must assume the worst-case skewed tree, making the time complexity O(n*h) where in the worst case h=n.

Space Complexity

O(N) – The provided solution calculates the height of the tree which takes constant space. The solution then iterates through each level and each node. For each level, a list is created to store the node values belonging to that level. In the worst-case scenario, where the binary tree is a complete binary tree, the widest level will contain approximately N/2 nodes (where N is the total number of nodes in the tree). This translates to needing to store roughly N/2 node values at some point, giving a space complexity of O(N).

Optimal Solution

Approach

The task is to visit every level of the tree and collect the nodes at each level in order. We will accomplish this by processing the tree level by level, making sure we visit all nodes at a particular level before going deeper. The key is to remember which node belongs to which level.

Here's how the algorithm would work step-by-step:

Start by putting the very top node (the root) into a special waiting list, considering it to be on level one.
While there are still nodes in our waiting list, we will repeat the following steps.
Process all nodes currently on the waiting list, as they represent the current level. As we process them, write down their values in left-to-right order.
For each node we process, if it has children (nodes connected below it), we will add these children to the end of our waiting list. The left child goes in the waiting list before the right child.
Continue this process until the waiting list is empty, meaning we have visited every node in the tree.

Code Implementation

from collections import deque

def levelOrder(root):
    if not root:
        return []

    result = []
    nodes_queue = deque([root])

    # Iterate while there are nodes to process
    while nodes_queue:
        level_size = len(nodes_queue)
        current_level = []

        # Process all nodes at the current level
        for _ in range(level_size):
            node = nodes_queue.popleft()
            current_level.append(node.val)

            # Add the left child if it exists
            if node.left:
                nodes_queue.append(node.left)

            # Add the right child if it exists
            if node.right:
                nodes_queue.append(node.right)

        result.append(current_level)

    return result

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

def level_order_traversal(root):
    if not root:
        return []

    results = []
    queue_of_nodes = deque([root])

    # Continue as long as nodes exist on the queue
    while queue_of_nodes:
        level_length = len(queue_of_nodes)
        current_level_nodes = []

        # Process nodes on current level
        for _ in range(level_length):
            node_being_processed = queue_of_nodes.popleft()
            current_level_nodes.append(node_being_processed.val)

            # Left child is enqueued next
            if node_being_processed.left:
                queue_of_nodes.append(node_being_processed.left)

            # Right child is enqueued last
            if node_being_processed.right:
                queue_of_nodes.append(node_being_processed.right)

        results.append(current_level_nodes)

    return results

Big(O) Analysis

Time Complexity

O(n) – We visit each of the n nodes in the binary tree exactly once. The while loop iterates until the waiting list (queue) is empty, and inside this loop, we process each node on the current level. For each node, we perform a constant amount of work: appending its value to the result list and adding its children to the queue. Therefore, the time complexity is directly proportional to the number of nodes in the tree, which is O(n).

Space Complexity

O(W) – The primary auxiliary space is used by the waiting list (queue). In the worst-case scenario, the waiting list will hold all the nodes at the widest level of the tree. Therefore, the space complexity is proportional to the maximum width (W) of the tree. N represents the total number of nodes in the tree. In a complete binary tree, the last level constitutes about half of all nodes so W can approach N/2 in the worst-case scenario but in sparse trees with one very wide level it can be smaller. The level order traversal uses a queue to hold the nodes at the current level, and the size of this queue dictates the auxiliary space. In the worst-case, the queue could hold all nodes at the widest level, resulting in O(W) space complexity.

Edge Cases

Case	How to Handle
Null or empty root node	Return an empty list immediately since there is nothing to traverse.
Single node tree (only root)	Return a list containing a single list with the root's value.
Completely skewed tree (all nodes on one side)	The queue will grow linearly with the number of nodes, and the algorithm should still process all levels correctly, though space complexity might be a concern for very large trees.
Perfectly balanced tree	The algorithm should handle balanced trees efficiently, and space complexity will be logarithmic with respect to the number of nodes.
Tree with duplicate node values	Duplicate node values don't affect the level order traversal logic as it focuses on the structure of the tree, not the values themselves.
Large tree (approaching memory limits)	Be mindful of memory usage as the queue grows with the width of the tree, potentially causing memory exhaustion for very large trees; iterative solutions are typically better in Python to avoid recursion limits.
Tree with negative and positive values	The algorithm works correctly with both positive and negative values, as it is agnostic to the value range.
Tree with a wide shallow structure compared to a deep narrow structure.	The algorithm should correctly traverse both, but the space complexity using BFS is dependent on the width of the tree.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the node values in the binary tree?
Can the binary tree be empty (i.e., root is null)? If so, what should I return?
Are the node values guaranteed to be integers, or could they be other data types like floats?
Do I need to handle the case where the tree is very deep or wide, potentially leading to memory constraints?
Is there an upper bound on the number of nodes in the tree?

Brute Force Solution

Approach

We want to visit all nodes of the tree level by level. The brute force method is like exploring every single possible path to each level of the tree, without any particular strategy.

Here's how the algorithm would work step-by-step:

First, figure out the height of the tree. This tells us how many levels we have to visit.
Then, for each level, go through every single node in the tree and check if that node belongs to the current level.
If a node belongs to the current level, we add its value to a list representing that level.
We do this by checking all nodes for level 1, then all nodes for level 2, and so on, until we have processed all levels.
Finally, we put the lists for each level together, in order from top to bottom, to get the final level order traversal.

Code Implementation

def level_order_brute_force(root):
    def get_tree_height(node):
        if not node:
            return 0
        left_height = get_tree_height(node.left)
        right_height = get_tree_height(node.right)
        return max(left_height, right_height) + 1

    def get_nodes_at_level(node, level, current_level, level_nodes):
        if not node:
            return

        # If we've reached the target level, append the node's value.
        if current_level == level:
            level_nodes.append(node.val)
            return

        get_nodes_at_level(node.left, level, current_level + 1, level_nodes)
        get_nodes_at_level(node.right, level, current_level + 1, level_nodes)

    if not root:
        return []

    tree_height = get_tree_height(root)
    result = []

    # Iterate through each level of the tree.
    for level in range(1, tree_height + 1):

        level_nodes_list = []
        #For each level, retrieve the nodes at each level
        get_nodes_at_level(root, level, 1, level_nodes_list)

        result.append(level_nodes_list)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by putting the very top node (the root) into a special waiting list, considering it to be on level one.
While there are still nodes in our waiting list, we will repeat the following steps.
Process all nodes currently on the waiting list, as they represent the current level. As we process them, write down their values in left-to-right order.
For each node we process, if it has children (nodes connected below it), we will add these children to the end of our waiting list. The left child goes in the waiting list before the right child.
Continue this process until the waiting list is empty, meaning we have visited every node in the tree.

Code Implementation

from collections import deque

def levelOrder(root):
    if not root:
        return []

    result = []
    nodes_queue = deque([root])

    # Iterate while there are nodes to process
    while nodes_queue:
        level_size = len(nodes_queue)
        current_level = []

        # Process all nodes at the current level
        for _ in range(level_size):
            node = nodes_queue.popleft()
            current_level.append(node.val)

            # Add the left child if it exists
            if node.left:
                nodes_queue.append(node.left)

            # Add the right child if it exists
            if node.right:
                nodes_queue.append(node.right)

        result.append(current_level)

    return result

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

def level_order_traversal(root):
    if not root:
        return []

    results = []
    queue_of_nodes = deque([root])

    # Continue as long as nodes exist on the queue
    while queue_of_nodes:
        level_length = len(queue_of_nodes)
        current_level_nodes = []

        # Process nodes on current level
        for _ in range(level_length):
            node_being_processed = queue_of_nodes.popleft()
            current_level_nodes.append(node_being_processed.val)

            # Left child is enqueued next
            if node_being_processed.left:
                queue_of_nodes.append(node_being_processed.left)

            # Right child is enqueued last
            if node_being_processed.right:
                queue_of_nodes.append(node_being_processed.right)

        results.append(current_level_nodes)

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty root node	Return an empty list immediately since there is nothing to traverse.
Single node tree (only root)	Return a list containing a single list with the root's value.
Completely skewed tree (all nodes on one side)	The queue will grow linearly with the number of nodes, and the algorithm should still process all levels correctly, though space complexity might be a concern for very large trees.
Perfectly balanced tree	The algorithm should handle balanced trees efficiently, and space complexity will be logarithmic with respect to the number of nodes.
Tree with duplicate node values	Duplicate node values don't affect the level order traversal logic as it focuses on the structure of the tree, not the values themselves.
Large tree (approaching memory limits)	Be mindful of memory usage as the queue grows with the width of the tree, potentially causing memory exhaustion for very large trees; iterative solutions are typically better in Python to avoid recursion limits.
Tree with negative and positive values	The algorithm works correctly with both positive and negative values, as it is agnostic to the value range.
Tree with a wide shallow structure compared to a deep narrow structure.	The algorithm should correctly traverse both, but the space complexity using BFS is dependent on the width of the tree.