Jobs

Interviews

Discussions

Populating Next Right Pointers in Each Node II

Medium

Amazon

2 views

Topics:

Trees

Given a perfect binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree, your function should populate each next pointer to point to its next right node, just like in the output. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

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

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Populating Next Right Pointers in Each Node II

Medium

Amazon

2 views

Topics:

Trees

Given a perfect binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree, your function should populate each next pointer to point to its next right node, just like in the output. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

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

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

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 that the nodes can hold?
Is the input tree guaranteed to be a perfect binary tree, or can it be any arbitrary binary tree?
If a node has no next right node, should its 'next' pointer point to null, or should it remain uninitialized?
Can the root node be null?
Are we modifying the original tree in-place, or is a new tree structure expected as output?

Brute Force Solution

Approach

The brute force approach to connecting nodes at the same level in a tree involves examining every single node and, for each, exhaustively searching for the next node on the same level. It’s like manually checking every connection for each node without any shortcuts. It guarantees finding the solution but might take a lot of work.

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

Start at the very top of the tree (the root).
For the starting node, check every other node in the entire tree to see if it's on the same level.
If you find a node on the same level, connect the starting node to that node.
If you find more than one node on the same level, connect to the closest one from left to right.
Move to the next node in the tree (any order is fine).
Repeat the process of checking every other node to find a same-level connection.
Continue this process for every single node in the tree until all nodes have been checked.

Code Implementation

def connect_brute_force(root):
    if not root:
        return root

    all_nodes = []
    def traverse(node):
        if node:
            all_nodes.append(node)
            traverse(node.left)
            traverse(node.right)
    traverse(root)

    for current_node in all_nodes:
        next_right = None
        min_distance = float('inf')

        for potential_neighbor in all_nodes:

            if current_node != potential_neighbor:
                # Find nodes at same level
                if get_level(root, current_node, 1) == get_level(root, potential_neighbor, 1):

                    distance = all_nodes.index(potential_neighbor) - all_nodes.index(current_node)
                    # Ensure next node is to the right
                    if distance > 0 and distance < min_distance:
                        min_distance = distance
                        next_right = potential_neighbor

        current_node.next = next_right

    return root

def get_level(root_node, target_node, level):
    if not root_node:
        return 0
    if root_node == target_node:
        return level
    downlevel = get_level(root_node.left, target_node, level + 1)
    if downlevel != 0:
        return downlevel
    downlevel = get_level(root_node.right, target_node, level + 1)
    return downlevel

Big(O) Analysis

Time Complexity

O(n³) – For each of the n nodes in the tree, the algorithm potentially examines all other nodes to find the next right node at the same level. To determine if two nodes are on the same level, a level calculation might require traversing the tree from the root, potentially visiting all nodes in the worst case, leading to O(n) time for level determination. Since we perform this level check (potentially O(n)) for each pair of nodes among n nodes, the total runtime approximates to n * (n * n), simplifying to O(n³).

Space Complexity

O(1) – The described brute force approach iterates through the tree, but it doesn't explicitly create any auxiliary data structures like lists, queues, or stacks to store tree nodes or intermediate results. The algorithm only uses a constant amount of extra memory to keep track of the current node being processed and another node to compare with on the same level. Therefore, the auxiliary space complexity remains constant irrespective of the number of nodes, N, in the tree. The space required doesn't scale with the input size, making it O(1).

Optimal Solution

Approach

The key is to use the existing next-level connections to your advantage while traversing level by level. We use already established links to navigate and connect nodes on each level without needing extra memory.

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

Start at the very top of the tree.
Keep track of the very first node of each level you are processing, so you can start the next level correctly.
For each node, check if it has a left child. If it does, connect the left child to the next available node on the same level. If no next available node on the same level exists, do nothing.
Then, check if the node has a right child and do the same thing: connect to the next available node on the same level.
The 'next available node' is either the node to the right already connected on the level, or if null, the next potential node to the right to be connected.
Move to the next node on the current level using the 'next' pointer that was already established in a previous iteration.
Once you've processed an entire level, move down to the first node of the next level and repeat the process until you've reached the bottom of the tree.

Code Implementation

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

def connect(root):
    if not root:
        return root

    head = root

    while head:
        current_node = head
        next_level_head = None
        previous_node = None

        # Iterate through the current level
        while current_node:
            # Connect left child
            if current_node.left:
                if not next_level_head:
                    next_level_head = current_node.left

                if previous_node:
                    previous_node.next = current_node.left

                previous_node = current_node.left

            # Connect right child
            if current_node.right:
                if not next_level_head:
                    next_level_head = current_node.right

                if previous_node:
                    previous_node.next = current_node.right

                previous_node = current_node.right

            # Move to the next node on the current level
            current_node = current_node.next

        # Move to the next level
        head = next_level_head

    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the tree exactly once. The outer loop iterates through each level, and the inner loop iterates through each node on that level using the 'next' pointers. Since each node's 'next' pointer is set only once and each node is visited only once during the traversal, the total number of operations is directly proportional to the number of nodes, n, in the tree. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided plain English explanation details an iterative level-by-level traversal of the tree, utilizing existing 'next' pointers to navigate. It only mentions the need to keep track of the 'first node of each level', but this is a single node reference. The algorithm doesn't involve any auxiliary data structures like arrays, hash maps, or queues that would scale with the input size N (number of nodes). Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Null root node	Return null immediately, as there's nothing to connect.
Single node tree	The next pointer of the root remains null, as there are no other nodes to connect to on the same level.
Complete binary tree	The algorithm should correctly link all nodes on each level from left to right.
Skewed tree (left or right)	The iterative level-order traversal must handle potentially missing child nodes on each level correctly.
Tree with varying depths of subtrees	The level-order traversal ensures the algorithm links nodes on a level regardless of subtree depth differences.
Tree with only left children present	The algorithm should correctly identify and link next nodes using the inner while loop conditions.
Tree with only right children present	The algorithm should correctly identify and link next nodes using the inner while loop conditions.
Large tree (memory constraints)	Level order traversal uses O(W) space where W is the maximum width of the tree; iterative solution is preferable to recursive for very deep trees.

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 that the nodes can hold?
Is the input tree guaranteed to be a perfect binary tree, or can it be any arbitrary binary tree?
If a node has no next right node, should its 'next' pointer point to null, or should it remain uninitialized?
Can the root node be null?
Are we modifying the original tree in-place, or is a new tree structure expected as output?

Brute Force Solution

Approach

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

Start at the very top of the tree (the root).
For the starting node, check every other node in the entire tree to see if it's on the same level.
If you find a node on the same level, connect the starting node to that node.
If you find more than one node on the same level, connect to the closest one from left to right.
Move to the next node in the tree (any order is fine).
Repeat the process of checking every other node to find a same-level connection.
Continue this process for every single node in the tree until all nodes have been checked.

Code Implementation

def connect_brute_force(root):
    if not root:
        return root

    all_nodes = []
    def traverse(node):
        if node:
            all_nodes.append(node)
            traverse(node.left)
            traverse(node.right)
    traverse(root)

    for current_node in all_nodes:
        next_right = None
        min_distance = float('inf')

        for potential_neighbor in all_nodes:

            if current_node != potential_neighbor:
                # Find nodes at same level
                if get_level(root, current_node, 1) == get_level(root, potential_neighbor, 1):

                    distance = all_nodes.index(potential_neighbor) - all_nodes.index(current_node)
                    # Ensure next node is to the right
                    if distance > 0 and distance < min_distance:
                        min_distance = distance
                        next_right = potential_neighbor

        current_node.next = next_right

    return root

def get_level(root_node, target_node, level):
    if not root_node:
        return 0
    if root_node == target_node:
        return level
    downlevel = get_level(root_node.left, target_node, level + 1)
    if downlevel != 0:
        return downlevel
    downlevel = get_level(root_node.right, target_node, level + 1)
    return downlevel

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the very top of the tree.
Keep track of the very first node of each level you are processing, so you can start the next level correctly.
For each node, check if it has a left child. If it does, connect the left child to the next available node on the same level. If no next available node on the same level exists, do nothing.
Then, check if the node has a right child and do the same thing: connect to the next available node on the same level.
The 'next available node' is either the node to the right already connected on the level, or if null, the next potential node to the right to be connected.
Move to the next node on the current level using the 'next' pointer that was already established in a previous iteration.
Once you've processed an entire level, move down to the first node of the next level and repeat the process until you've reached the bottom of the tree.

Code Implementation

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

def connect(root):
    if not root:
        return root

    head = root

    while head:
        current_node = head
        next_level_head = None
        previous_node = None

        # Iterate through the current level
        while current_node:
            # Connect left child
            if current_node.left:
                if not next_level_head:
                    next_level_head = current_node.left

                if previous_node:
                    previous_node.next = current_node.left

                previous_node = current_node.left

            # Connect right child
            if current_node.right:
                if not next_level_head:
                    next_level_head = current_node.right

                if previous_node:
                    previous_node.next = current_node.right

                previous_node = current_node.right

            # Move to the next node on the current level
            current_node = current_node.next

        # Move to the next level
        head = next_level_head

    return root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return null immediately, as there's nothing to connect.
Single node tree	The next pointer of the root remains null, as there are no other nodes to connect to on the same level.
Complete binary tree	The algorithm should correctly link all nodes on each level from left to right.
Skewed tree (left or right)	The iterative level-order traversal must handle potentially missing child nodes on each level correctly.
Tree with varying depths of subtrees	The level-order traversal ensures the algorithm links nodes on a level regardless of subtree depth differences.
Tree with only left children present	The algorithm should correctly identify and link next nodes using the inner while loop conditions.
Tree with only right children present	The algorithm should correctly identify and link next nodes using the inner while loop conditions.
Large tree (memory constraints)	Level order traversal uses O(W) space where W is the maximum width of the tree; iterative solution is preferable to recursive for very deep trees.