Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Connect Level Order Siblings

Problem Statement

Given a root of the binary tree, connect each node with its level order successor. The last node of each level should point to a null node.

Examples

Example 1:

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
  • Output: 
    [1 -> null]
[2 -> 3 -> null]
[4 -> 5 -> 6 -> 7 -> null]
  • Explanation:
    The tree is traversed level by level using BFS. Each node is connected to its next right node at the same level. The last node of each level points to null.

Example 2:

  • Input: root = [12, 7, 1, 9, null, 10, 5]
  • **Output:

.....

.....

.....

Like the course? Get enrolled and start learning!
G

greenwald.juj

· 3 years ago

All the previous Tree BFS Level Order Examples are returning something, why aren't we doing it here? Is it inherent that the tree is being returned?

Also why does this one include the print function but previous versions don't? This makes it so you don't see the input and output when the Solution is Executed.

from __future__ import print_function
from collections import deque


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

  # level order traversal using 'next' pointer
  def print_level_order(self):
    nextLevelRoot = self
    while nextLevelRoot:
      current = nextLevelRoot
      nextLevelRoot = None
      while current:
        print(str(current.val) + " ", end='')
        if not nextLevelRoot
A

Avinash Agarwal

· 4 years ago

public TreeNode connect(TreeNode root) {

if (root == null) { return root; }

// Start with the root node. There are no next pointers // that need to be set up on the first level Node leftmost = root;

// Once we reach the final level, we are done while (leftmost.left != null) {

// Iterate the "linked list" starting from the head // node and using the next pointers, establish the // corresponding links for the next level Node head = leftmost;

while (head != null) {

// CONNECTION 1 head.left.next = head.right;

// CONNECTION 2 if (head.next != null) { head.right.next = head.next.left; }

// Progress along the list (nodes on the current level) head = head.next; }

// Move onto the next level leftmost = leftmost.left; }

return root; }

This is a solution with O(1) space.

Show 2 replies
Ahmed k

Ahmed k

· 4 years ago

// levelSize static void connect(TreeNode *root) { if (!root) return;

queue nodes_queue; nodes_queue.push(root);

while(!nodes_queue.empty()) { int levelSize = nodes_queue.size();

while(levelSize--) { TreeNode* current = nodes_queue.front();

if(current->left) nodes_queue.push(current->left); if(current->right) nodes_queue.push(current->right);

if(!levelSize) { // 0 current->next = NULL; nodes_queue.pop(); break; }

nodes_queue.pop();

current->next = nodes_queue.front(); } } }

L

lejafilip

· 2 years ago

{
   std::queue<TreeNode*> nodes;

    nodes.push(root);
    while(!nodes.empty())
    {
      std::queue<TreeNode*> nodesInLevel; // <- this one
      auto level = nodes.size();
      for(auto i = 0; i < level; ++i)
      {
        auto node = nodes.front();
        nodes.pop();
        nodesInLevel.push(node);

        if(node->left)
          nodes.push(node->left);

        if(node->right)
          nodes.push(node->right);
      }

      while(!nodesInLevel.empty())
      {
        auto prev = nodesInLevel.front();
        nodesInLevel.pop();

        if(!nodesInLevel.empty())
        {

          auto curr = nodesInLevel.front();
          prev->next = curr;

        }
      }
    }

    return root;
}
//It still has generally O(n) space complexity but simplified from O(n/2 +
Parikshit Murria

Parikshit Murria

· a year ago

import java.util.*;

/*class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode next;

  TreeNode(int x) {
    val = x;
    left = right = next = null;
  }
};*/

class Solution {
  public TreeNode connect(TreeNode root) {
    if (root == null) {
      return root;
    }
    solve(root);
    return root;
  }

  public void solve(TreeNode root) {

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

    while(!queue.isEmpty()) {

      int levelSize = queue.size();

      for (int i = 0; i<levelSize; i++) {

        TreeNode node = queue.poll();

        if (i == levelSize-1) {
          node.next = null;
        } else {
	        node.next = queue.peek();
        }

        if (node.left != null) {
          queue.offer(node.left);
        }